幾乎完全圖是由第二Immanantal多項(xiàng)式刻畫(huà)的①

曾曉琳， 吳廷增， 潘佳麗

青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西寧 810007

其中χ表示Sn關(guān)于劃分(2,1,…,1)的不可約特征標(biāo).令G是一個(gè)含有n個(gè)頂點(diǎn)的圖,L(G)表示圖G的拉普拉斯矩陣.多項(xiàng)式d2(xI-L(G))表示圖G的第二imamnantal多項(xiàng)式,其中I表示n階單位矩陣.本文證明了幾乎完全圖是由第二imamnantal多項(xiàng)式確定的．

一個(gè)n階矩陣A=(aij)(i,j∈{1,2,…,n})的第二immanant定義為

其中χ是Sn關(guān)于劃分(2,1,…,1)的不可約特征標(biāo).特別地,χ(σ)=ε(σ)[F(σ)-1],其中ε是交替特征標(biāo),F是固定點(diǎn)的個(gè)數(shù)．

第二immanant是積和式與行列式之間的一個(gè)不變量.文獻(xiàn)[1]指出計(jì)算第二immanant的時(shí)間復(fù)雜度是n4.假設(shè)矩陣A的階為n(≥2),因?yàn)閐2(A)的項(xiàng)對(duì)應(yīng)于detA的因子(F(σ)-1)(σ∈Sn).因此有

(1)

其中A(i)是刪除矩陣A的第i行和第i列得到的子矩陣.例如,假設(shè)

根據(jù)公式(1),可得d2(A)=18．

令G是含有n個(gè)頂點(diǎn)的圖.A(G)是圖G的(0,1)-鄰接矩陣.di表示頂點(diǎn)vi的度.矩陣

L(G)=D(G)-A(G)

稱(chēng)為圖G的拉普拉斯矩陣,其中D(G)是對(duì)角元素為{d1,d2,…,dn}的n階度矩陣．

多項(xiàng)式

稱(chēng)作圖G的第二immanantal多項(xiàng)式,記作d2-多項(xiàng)式,其中I是n×n單位矩陣.為了強(qiáng)調(diào)圖G,系數(shù)通常記作ck(G)(0≤k≤n)．

兩個(gè)圖是共第二immanant的,是指這兩個(gè)圖分享相同的第二immanantal多項(xiàng)式.圖H與圖G是共第二immanant的,但不是同構(gòu)的,則稱(chēng)H是G的一個(gè)共第二immanant伙伴.如果圖G沒(méi)有共第二immanant伙伴,則稱(chēng)圖G是由第二immanantal多項(xiàng)式確定的．

圖譜理論中的一個(gè)經(jīng)典問(wèn)題: 什么樣的圖是由多項(xiàng)式確定的?在圖多項(xiàng)式理論中,這是一個(gè)困難的問(wèn)題.近幾年,這個(gè)問(wèn)題受到了許多學(xué)者的關(guān)注.一些圖G已經(jīng)被證明是由矩陣(xI-L(G))的行列式確定的,例如雙星狀圖[2]、沙漏圖[3]、Zn圖[4]、T-形樹(shù)[5]、∞-圖[6]等．

最近,學(xué)者們考慮了什么樣的圖是由矩陣(xI-L(G))的積和式確定的.文獻(xiàn)[7]證明了完全圖和圈是由矩陣(xI-L(G))的積和式確定的.文獻(xiàn)[8]證明了棒棒糖圖是由(xI-L(G))的積和式確定的.關(guān)于這個(gè)問(wèn)題更多的研究,可參見(jiàn)文獻(xiàn)[9-18]．

文獻(xiàn)[19]首次考慮了一個(gè)問(wèn)題: 什么樣的圖是由d2-多項(xiàng)式確定的? 文獻(xiàn)[19]證明了: 幾乎所有的樹(shù)都有共第二immanant伙伴.特別地,文獻(xiàn)[1]證明了: 如果圖G和H是兩個(gè)正則圖,則G和H是共第二immanant的當(dāng)且當(dāng)

det(xI-L(G))=det(xI-L(H))

或

det(xI-A(G))=det(xI-A(H))

并且,文獻(xiàn)[10]發(fā)現(xiàn)一對(duì)非正則的圖對(duì)是共第二immanant的,如圖1所示．

圖1 非正則的且共第二immanant的圖對(duì)

基于文獻(xiàn)[19]的探討,存在一個(gè)有趣的問(wèn)題: 尋找一些圖,既是由d2-多項(xiàng)式確定的,也是由特征多項(xiàng)式det(xI-A(G))確定的.本文圍繞這個(gè)問(wèn)題開(kāi)展研究．

令Gn是從完全圖Kn刪除至多5條邊得到的圖集.文獻(xiàn)[20]證明了Gn中所有的圖都是由其特征多項(xiàng)式確定的.本文討論Gn中哪些圖是由其第二immanantal多項(xiàng)式確定的.意外的是,我們發(fā)現(xiàn),無(wú)例外地,Gn中所有的圖都是由其第二imamnantal多項(xiàng)式確定的．

定理1Gn中所有的圖都是由其第二immanantal多項(xiàng)式確定的．

本文剩余內(nèi)容的結(jié)構(gòu)如下: 先給出一些d2-多項(xiàng)式的性質(zhì); 再給出定理1的證明; 最后提出兩個(gè)值得未來(lái)進(jìn)一步研究的有意義的問(wèn)題．

令圖G=(V,E)表示一個(gè)含有非空點(diǎn)集V和非空邊集E的無(wú)向簡(jiǎn)單圖,即G是不含有環(huán)和重邊的圖．

文獻(xiàn)[21]指出,對(duì)n≥10,在Gn中存在45個(gè)非同構(gòu)圖,并標(biāo)記為Gij(i=1,2,…,5;j=0,1,…,25),如圖2所示．

圖2 從完全圖Kn中刪除至多5條邊得到的圖集Gn

引理1[1]令G是含有n個(gè)頂點(diǎn)和m條邊的連通圖,(d1,d2,…,dn)表示圖G的度序列,L(G)是圖G的拉普拉斯矩陣,且

則

c0(G)=n-1

c1(G)=2m(n-1)

cn(G)=2mτ(G)

其中τ(G)表示圖G的生成樹(shù)的個(gè)數(shù)．

由引理1,我們可以得到d2-多項(xiàng)式的一些性質(zhì)．

引理2從圖G的d2-多項(xiàng)式的系數(shù)c0(G),c1(G)和cn(G)可以推斷出G的頂點(diǎn)數(shù)、邊數(shù)、生成樹(shù)的個(gè)數(shù)．

其中τ(G)是G的生成樹(shù)的個(gè)數(shù)．

由引理3,我們計(jì)算出了Gn中一些圖的生成樹(shù)的個(gè)數(shù),如表1所示．

表1 Gn中圖的生成樹(shù)的個(gè)數(shù)

由引理3,我們可得:

定理2圖G10是由d2-多項(xiàng)式確定的．

定理3圖G20和G21是由d2-多項(xiàng)式確定的．

證根據(jù)表1,我們知道

τ(G20)-τ(G21)=nn-4(n2-4n+3)-nn-4(n2-4n+4)≠0

由引理2可知,這意味著G20和G21是由d2-多項(xiàng)式確定的．

定理4圖G30,G31,G32,G33和G34是由d2-多項(xiàng)式確定的．

證根據(jù)G3i(i=0,1,…,4)的圖結(jié)構(gòu),我們知道

|V(G30)|≥4 |V(G31)|≥5 |V(G32)|≥3 |V(G33)|≥4 |V(G34)|≥6

與定理3類(lèi)似,根據(jù)表1可得,只有當(dāng)n=4時(shí),

τ(G32)-τ(G33)=(-n+4)nn-5=0

根據(jù)引理1,我們可以得到

c2(G32)=33c2(G33)=36

這意味著G32和G33不是共第二immanant的．

同樣地,解方程

τ(G30)-τ(G31)=nn-5(-2n+2)=0

τ(G31)-τ(G32)=(2n-6)nn-5=0

τ(G31)-τ(G33)=(n-2)nn-5=0

τ(G31)-τ(G34)=(2-n)nn-5=0

τ(G33)-τ(G34)=(-2n+4)nn-5=0

我們得到這些方程的解n小于對(duì)應(yīng)圖的頂點(diǎn)數(shù),矛盾.所以,G31和G33,G31和G34,G33和G34分別都不是共第二immanant的．

由表1,解方程

τ(G30)-τ(G32)=0τ(G30)-τ(G33)=0

τ(G30)-τ(G34)=0τ(G32)-τ(G34)=0

可以得出這些方程或者沒(méi)有解,或者沒(méi)有整數(shù)解．

由引理2及以上的討論可知,圖G30,G31,G32,G33和G34是由d2-多項(xiàng)式確定的．

定理5圖G40,G41,G42,G43,G44,G45,G46,G47,G48,G49和G4(10)是由d2-多項(xiàng)式確定的．

證根據(jù)圖G4j(j=0,1,…,10)的結(jié)構(gòu),我們可以得到|V(G40)|≥5,|V(G41)|≥6,|V(G42)|≥6,|V(G43)|≥7,|V(G44)|≥4,|V(G45)|≥5,|V(G46)|≥4,|V(G47)|≥5,|V(G48)|≥6,|V(G49)|≥8和|V(G4(10))|≥5．

由表1得到,只有當(dāng)n=4時(shí),τ(G44)-τ(G46)=(n-4)nn-5=0.如果n=4,由引理1,我們得到c2(G44)=16和c2(G46)=14.這表明G44和G46不是共第二immanant的．

同樣地,只有當(dāng)n=-1,5時(shí),有τ(G44)-τ(G47)=(-n2+4n-5)nn-6=0.如果n=5,由引理1可知,在圖G44和G47中,c2(G44)=212和c2(G47)=216.這意味著G44和G47不是共第二immanant的．

類(lèi)似地,只有當(dāng)n=1,5時(shí),τ(G46)-τ(G4(10))=(-n2+6n-5)nn-6=0.如果n=5,由引理1可得,c2(G46)=208和c2(G4(10))=212.這說(shuō)明G46和G4(10)不是共第二immanant的．

根據(jù)表1,解方程τ(G40)-τ(G4j)=0(j=1,2,3,5,6,10),τ(G41)-τ(G4j)=0(j=2,3,4,5,6,8,9,10),τ(G42)-τ(G4j)=0(j=3,5,6,7,8,10),τ(G43)-τ(G4j)=0(j=4,5,6,8,9,10),τ(G44)-τ(G4j)=0(j=5,8,9),τ(G45)-τ(G4j)=0(j=8,9),τ(G47)-τ(G4j)=0(j=8,10),τ(G48)-τ(G49)=0.我們得到這些方程的根n小于對(duì)應(yīng)圖的頂點(diǎn)數(shù),矛盾.因此,圖G40和圖G41,G42,G43,G45,G46,G4(10); 圖G41和圖G42,G43,G44,G45,G46,G48,G49,G4(10); 圖G42和圖G43,G45,G46,G47,G48,G4(10); 圖G43和圖G44,G45,G46,G49,G4(10); 圖G44和圖G45,G48,G49; 圖G45和圖G48,G49; 圖G47和圖G48,G4(10); 圖G48和圖G49都分別不是共第二immanant的．

由表1,解方程τ(G40)-τ(G4j)=0(j=4,7,8,9),τ(G41)-τ(G47)=0,τ(G42)-τ(G4j)=0(j=4,9),τ(G43)-τ(G47)=0,τ(G44)-τ(G4(10))=0,τ(G45)-τ(G4j)=0(j=6,7,10),τ(G46)-τ(G4j)=0(j=7,8,9),τ(G47)-τ(G49)=0,τ(G48)-τ(G4(10))=0和τ(G49)-τ(G4(10))=0.我們可以得出這些方程或者沒(méi)有解,或者沒(méi)有整數(shù)根.這說(shuō)明G40和G44,G47,G48,G49;G41和G47;G42和G44,G49;G43和G47;G44和G4(10);G45和G46,G47,G4(10);G46和G47G48,G49;G47和G49;G48和G4(10);G49和G4(10)都分別不是共第二immanant的．

根據(jù)引理2和上述討論可得,G40,G41,G42,G43,G44,G45,G46,G47,G48,G49和G4(10)是由d2-多項(xiàng)式確定的．

定理6圖G50,G51,G52,G53,G54,G55,G56,G57,G58,G59,G5(10),G5(11),G5(12),G5(13),G5(14),G5(15),G5(16),G5(17),G5(18),G5(19),G5(20),G5(21),G5(22),G5(23),G5(24)和G5(25)是由d2-多項(xiàng)式確定的．

證根據(jù)圖G5j(j=0,1,…,25)的結(jié)構(gòu),我們可得|V(G50)|≥8,|V(G51)|≥8,|V(G52)|≥9,|V(G53)|≥7,|V(G54)|≥6,|V(G55)|≥6,|V(G56)|≥7,|V(G57)|≥7,|V(G58)|≥8,|V(G59)|≥5, |V(G5(10))|≥5,|V(G5(11))|≥7,|V(G5(12))|≥5,|V(G5(13))|≥6,|V(G5(14))|≥7,|V(G5(15))|≥5,|V(G5(16))|≥4,|V(G5(17))|≥7,|V(G5(18))|≥6,|V(G5(19))|≥6,|V(G5(20))|≥5,|V(G5(21))|≥10,|V(G5(22))|≥6,|V(G5(23))|≥6,|V(G5(24))|≥6和|V(G5(25))|≥6．

與定理5的證明類(lèi)似,根據(jù)表1可得:

只有當(dāng)n=1,n=6時(shí),τ(G59)-τ(G5(24))=nn-7(-n3+8n2-13n+6)=0.如果n=6,由引理1可得c2(G59)=780和c2(G5(24))=790.這表明G59和G5(24)不是共第二immanant的．

只有當(dāng)n=1,n=5時(shí),τ(G5(10))-τ(G5(15))=nn-6(-n2+6n-5)=0.類(lèi)似地,如果n=5,根據(jù)引理1可得c2(G5(10))=106和c2(G5(15))=146.這說(shuō)明G5(10)和G5(15)不是共第二immanant的．

只有當(dāng)n=3,n=5時(shí),τ(G5(10))-τ(G5(16))=nn-6(n2-8n+15)=0 .如果n=5,由引理1得到c2(G5(10))=106和c2(G5(16))=138.這意味著G5(10)和G5(16)不是共第二immanant的．

只有當(dāng)n=2,5時(shí),τ(G5(15))-τ(G5(16))=nn-6(2n2-14n+20)=0.如果n=5,根據(jù)引理1可得c2(G5(15))=146和c2(G5(16))=138.這說(shuō)明G5(15)和G5(16)不是共第二immanant的．

只有當(dāng)n=-1,5時(shí),τ(G5(15))-τ(G5(20))=nn-6(-n2+4n-5)=0.如果n=5時(shí),由引理1得到c2(G5(15))=146和c2(G5(20))=150.這表明G5(15)和G5(20)不是共第二immanant的．

類(lèi)似地,根據(jù)表1,解方程τ(G50)-τ(G5j)=0(j=1,2,3,6,8,11,14,15,…,23),τ(G51)-τ(G5j)=0(j=1,10,20),τ(G52)-τ(G5j)=0(j=1,2,10,20),τ(G53)-τ(G5j)=0(j=1,2,3,10,12,13,20),τ(G54)-τ(G5j)=0(j=5,6,7,8,11,13,18,22,24,25),τ(G55)-τ(G5j)=0(j=6,7,8,9,11,12,13,18,20,22,23,24,25),τ(G56)-τ(G5j)=0(j=7,8,9,11,13,15,16,17,18,19,21,22,23,24,25),τ(G57)-τ(G5j)=0(j=8,10,11,12,13,14,17,18,19,20,22,24,25),τ(G58)-τ(G5j)=0(j=9,11,13,14,…,19,21,22,23,24,25),τ(G59)-τ(G5j)=0(j=10,11,12,13,14,18,22,25),τ(G5(10))-τ(G5j)=0(j=12,21,23),τ(G5(11))-τ(G5j)=0(j=12,13,14,…,19,21,22,23,24,25),τ(G5(12))-τ(G5j)=0(j=13,14,18,22,25),τ(G5(13))-τ(G5j)=0(j=14,18,22,24,25),τ(G5(14))-τ(G5j)=0(j=15,16,17,18,19,21,22,23,25),τ(G5(15))-τ(G5j)=0(j=17,18,19,21,22,23),τ(G5(16))-τ(G5j)=0(j=17,18,19,21,22,23),τ(G5(17))-τ(G5j)=0(j=18,19,…,23),τ(G5(18))-τ(G5j)=0(j=19,20,…,25),τ(G5(19))-τ(G5j)=0(j=21,22,23),τ(G5(20))-τ(G5(24))=0,τ(G5(21))-τ(G5j)=0(j=22,23),τ(G5(22))-τ(G5j)=0(j=23,24,25})和τ(G5(24))-τ(G5(25))=0.我們得到這些方程的根n小于對(duì)應(yīng)圖的頂點(diǎn)數(shù),矛盾.因此,G50和G5j(j=1,2,3,6,8,11,14,15,…,23),G51和G5j(j=1,10,20),G52和G5j(j=1,2,10,20),G53和G5j(j=1,2,3,10,12,13,20),G54和G5j(j=5,6,7,8,11,13,18,22,24,25),G55和G5j(j=6,7,8,9,11,12,13,18,20,22,23,24,25),G56和G5j(j=7,8,9,11,13,15,16,17,18,19,21,22,23,24,25),G57和G5j(j= 8,10,11,12,13,14,17,18,19,20,22,24,25),G58和G5j(j=11,13,14,…,19,21,22,23,24,25),G59和G5j(j=10,11,12,13,14,18,22,25),G5(10)和G5j(j=12,21,23),G5(11)和G5j(j=12,13,14,…,19,21,22,23,24,25),G5(12)和G5j(j=13,14,18,22,25),G5(13)和G5j(j=14,18,22,24,25),G5(14)和G5j(j=15,16,17,18,19,21,22,23,25),G5(15)和G5j(j=17,18,19,21,22,23),G5(16)和G5j(j=17,18,19,21,22,23),G5(17)和G5j(j=18,19,…,23),G5(18)和G5j(j=19,20,…,25),G5(19)和G5j(j=21,22,23),G5(20)和G5(24),G5(21)和G5j(j=22,23),G5(22)和G5j(j=23,24,25),G5(24)和G5(25)都分別不是共第二immanant的．

同樣地,根據(jù)表1,解方程τ(G50)-τ(G5j)=0(j=4,5,7,9,10,12,13,24,25),τ(G51)-τ(G5j)=0(j=10,20),τ(G52)-τ(G5j)=0(j=10,20),τ(G53)-τ(G5j)=0(j=10,12,13,20),τ(G54)-τ(G5j)=0(j= 9,10,12,14,15,16,17,19,20,21,23),τ(G55)-τ(G5j)=0(j=10,14,15,16,17,19,21),τ(G56)-τ(G5j)=0(j=10,12,14,20),τ(G57)-τ(G5j)=0(j=9,15,16,21,23),τ(G58)-τ(G5j)=0(j=10,12,20),τ(G59)-τ(G5j)=0(j=15,16,17,19,20,21,23),τ(G5(10))-τ(G5j)=0(j=11,13,14,17,18,19,20,22,24,25),τ(G5(11))-τ(G5(20))=0,τ(G5(12))-τ(G5j)=0(j=15,16,17,19,20,21,23,24),τ(G5(13))-τ(G5j)=0(j=15,16,17,19,20,21,23),τ(G5(14))-τ(G5j)=0(j=20,24),τ(G5(15))-τ(G5j)=0(j=24,25),τ(G5(16))-τ(G5j)=0(j=20,24,25),τ(G5(17))-τ(G5j))=0(j=24,25),τ(G5(19))-τ(G5j)=0(j= 20,24,25),τ(G5(20))-τ(G5j)=0(j=21,22,23,25),τ(G5(21))-τ(G5j)=0(j=24,25)和τ(G5(23))-τ(G5j)=0(j=24,25).我們可以得到這些方程或者沒(méi)有解,或者沒(méi)有整數(shù)根.因此,G50和G5j(j=4,5,7,9,10,12,13,24,25),G51和G5j(j=10,20),G52和G5j(j=10,20),G53和G5j(j=10,12,13,20),G54和G5j(j=9,10,12,14,15,16,17,19,20,21,23),G55和G5j(j=10,14,15,16,17,19,21),G56和G5j(j=10,12,14,20),G57和G5j(j=9,15,16,21,23),G58和G5j(j=10,12,20),G59和G5j(j=15,16,17,19,20,21,23),G5(10)和G5j(j=11,13,14,17,18,19,20,22,24,25),G5(11)和G5(20),G5(12)和G5j(j=15,16,17,19,20,21,23,24),G5(13)和G5j(j=15,16,17,19,20,21,23),G5(14)和G5j(j=20,24),G5(15)和G5j(j=24,25),G5(16)和G5j(j=20,24,25),G5(17)和G5j(j=24,25),G5(19)和G5j(j=20,24,25),G5(20)和G5j(j=21,22,23,25),G5(21)和G5j(j=24,25),G5(23)和G5j(j=24,25) 都分別不是共第二immanant的．

由引理2和上述探討可知,G50,G51,G52,G53,G54,G55,G56,G57,G58,G59,G5(10),G5(11),G5(12),G5(13),G5(14),G5(15),G5(16),G5(17),G5(18),G5(19),G5(20),G5(21),G5(22),G5(23),G5(24)和G5(25)是由d2-多項(xiàng)式確定的．

結(jié)合定理2-定理6,定理1得證．

非同構(gòu)的圖有相同的immanantal多項(xiàng)式的例子已經(jīng)被給了出來(lái).因此,刻畫(huà)由d2-多項(xiàng)式確定的圖是一個(gè)有趣的問(wèn)題.本文證明了所有的幾乎完全圖都是由d2-多項(xiàng)式確定的.另外,我們發(fā)現(xiàn)兩個(gè)值得進(jìn)一步研究的問(wèn)題:

問(wèn)題2構(gòu)造一個(gè)從完全圖Kn中刪除l條邊得到的圖對(duì),使得它們是共第二immanant的．