幾乎完全圖是由第二Immanantal多項式刻畫的①

曾曉琳， 吳廷增， 潘佳麗

青海民族大學 數學與統計學院，西寧 810007

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

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

其中χ是Sn關于劃分(2,1,…,1)的不可約特征標.特別地,χ(σ)=ε(σ)[F(σ)-1],其中ε是交替特征標,F是固定點的個數．

第二immanant是積和式與行列式之間的一個不變量.文獻[1]指出計算第二immanant的時間復雜度是n4.假設矩陣A的階為n(≥2),因為d2(A)的項對應于detA的因子(F(σ)-1)(σ∈Sn).因此有

(1)

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

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

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

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

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

多項式

稱作圖G的第二immanantal多項式,記作d2-多項式,其中I是n×n單位矩陣.為了強調圖G,系數通常記作ck(G)(0≤k≤n)．

兩個圖是共第二immanant的,是指這兩個圖分享相同的第二immanantal多項式.圖H與圖G是共第二immanant的,但不是同構的,則稱H是G的一個共第二immanant伙伴.如果圖G沒有共第二immanant伙伴,則稱圖G是由第二immanantal多項式確定的．

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

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

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

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

或

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

并且,文獻[10]發現一對非正則的圖對是共第二immanant的,如圖1所示．

圖1 非正則的且共第二immanant的圖對

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

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

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

本文剩余內容的結構如下: 先給出一些d2-多項式的性質; 再給出定理1的證明; 最后提出兩個值得未來進一步研究的有意義的問題．

令圖G=(V,E)表示一個含有非空點集V和非空邊集E的無向簡單圖,即G是不含有環和重邊的圖．

文獻[21]指出,對n≥10,在Gn中存在45個非同構圖,并標記為Gij(i=1,2,…,5;j=0,1,…,25),如圖2所示．

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

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

則

c0(G)=n-1

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

cn(G)=2mτ(G)

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

由引理1,我們可以得到d2-多項式的一些性質．

引理2從圖G的d2-多項式的系數c0(G),c1(G)和cn(G)可以推斷出G的頂點數、邊數、生成樹的個數．

其中τ(G)是G的生成樹的個數．

由引理3,我們計算出了Gn中一些圖的生成樹的個數,如表1所示．

表1 Gn中圖的生成樹的個數

由引理3,我們可得:

定理2圖G10是由d2-多項式確定的．

定理3圖G20和G21是由d2-多項式確定的．

證根據表1,我們知道

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

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

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

證根據G3i(i=0,1,…,4)的圖結構,我們知道

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

與定理3類似,根據表1可得,只有當n=4時,

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

根據引理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小于對應圖的頂點數,矛盾.所以,G31和G33,G31和G34,G33和G34分別都不是共第二immanant的．

由表1,解方程

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

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

可以得出這些方程或者沒有解,或者沒有整數解．

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

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

證根據圖G4j(j=0,1,…,10)的結構,我們可以得到|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得到,只有當n=4時,τ(G44)-τ(G46)=(n-4)nn-5=0.如果n=4,由引理1,我們得到c2(G44)=16和c2(G46)=14.這表明G44和G46不是共第二immanant的．

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

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

根據表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小于對應圖的頂點數,矛盾.因此,圖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.我們可以得出這些方程或者沒有解,或者沒有整數根.這說明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的．

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

定理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-多項式確定的．

證根據圖G5j(j=0,1,…,25)的結構,我們可得|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的證明類似,根據表1可得:

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

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

只有當n=3,n=5時,τ(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的．

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

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

類似地,根據表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小于對應圖的頂點數,矛盾.因此,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的．

同樣地,根據表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).我們可以得到這些方程或者沒有解,或者沒有整數根.因此,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-多項式確定的．

結合定理2-定理6,定理1得證．

非同構的圖有相同的immanantal多項式的例子已經被給了出來.因此,刻畫由d2-多項式確定的圖是一個有趣的問題.本文證明了所有的幾乎完全圖都是由d2-多項式確定的.另外,我們發現兩個值得進一步研究的問題:

問題2構造一個從完全圖Kn中刪除l條邊得到的圖對,使得它們是共第二immanant的．