單圈圖H(p,2K1,6)的拉普拉斯譜刻畫

趙紹玉

(三明學院 信息工程學院,福建 三明 365004)

這里考慮的是連通的簡單無向圖。令V(G)表示圖G的頂點集,E(G)表示其邊集,ni(G)表示G中度為i的頂點數(shù),A(G)=(aij)n×n表示其鄰接矩陣,當vi和vj在圖G中相鄰時,aij等于1,否則為0.di表示圖G中頂點vi的度數(shù)。D(G)=diag(d1,d2,…,dn)是由G中頂點的度構成的對角矩陣。矩、陣L(G)=D(G)-A(G)稱為圖G的拉普拉斯矩陣。多項式P(A(G),λ)=det(λIn-A(G))=λn+a1λn-1+…+an表示G的鄰接特征多項式,P(L(G),μ)=det(λIn-L(G))=μn+b1μn-1+…+bn表示G的拉普拉斯特征多項式,In是單位矩陣。設λi(i=1,…,n)是A(G)的特征值,它們的集合構成了圖G的鄰接譜;μi(i=1,…,n)是L(G)的特征值,它們構成的集合稱為圖G的拉普拉斯譜。如果兩個圖的鄰接譜是相同的,就稱它們是鄰接同譜圖。同樣,若兩個圖的拉普拉斯譜相同,則稱它們是拉普拉斯同譜圖。若與圖G鄰接同譜的圖都與G同構,稱圖G可由其鄰接譜確定。同樣,若與圖G拉普拉斯同譜的圖都與G同構,稱圖G可由其拉普拉斯譜確定。由于化學研究的需要,Günthard和Primas[1]在1956年提出了圖譜的確定問題;到了2003年,這一問題再次被Van Dam 和Haemers[2]提出,引起了廣泛的關注,陸續(xù)出現(xiàn)了很多研究成果,具體可參見文獻[3]。用H(p,tK1,m)表示具有tm+p個頂點的單圈圖,它是由圈Cp連續(xù)相鄰的t(1≤t≤p)個頂點分別與星K1,m的中心重合而得到的。盧鵬麗[4]證明了圖H(p,K1,m)是由它的拉普拉斯譜確定的;Bu等[5]證明了H(p,pK1,2)由它的拉普拉斯譜確定的; 王陸華[6]證明了圖H(p,(p-1)K1,2)是由它的拉普拉斯譜確定的,特別當p為偶數(shù)時,圖H(p,2K1,2),H(p,3K1,2),H(p,(p-3)K1,2),H(p,(p-2)K1,2)也都是由其拉普拉斯譜確定。梅若星等[7]證明了單圈圖3,H(p,pK1,4)和H(p,(p-1)K1,3)分別是由其拉普拉斯譜確定的。并且當p為偶數(shù)時,H(p,2K1,3),H(p,(p-3)K1,3)和H(p,(p-2)K1,3)也分別由其拉普拉斯譜確定。孫秋實等[8]證明了單圈圖H(p,pK1,5)和H(p,(p-1)K1,4)是由其拉普拉斯譜確定的,而且當p為偶數(shù)時,H(p,2K1,4),H(p,(p-3)K1,4)和H(p,(p-2)K1,4)也分別由其拉普拉斯譜確定。趙紹玉[9]證明了單圈圖H(p,pK1,6)是由其拉普拉斯譜確定的。對于單圈圖H(p,2K1,6)和H(p,pK1,m)(m>6)的拉普拉斯譜確定問題還沒有具體研究結果。本文證明了當p為偶數(shù)時,單圈圖H(p,2K1,6)(m>6)也是由它的拉普拉斯譜確定。

1 基本引理

引理1[3]若兩個圖是拉普拉斯同譜圖,則它們的頂點數(shù)和邊數(shù)相同;并且兩圖所有頂點度的平方和相等;若兩個圖是鄰接同譜圖,則它們具有相同的頂點數(shù)、邊數(shù)和任意長度的閉回路數(shù)。

引理2[10]設連通圖G是含有圈Ck的單圈圖。若圖G′與圖G具有相同的拉普拉斯譜,則圖G′也是含有圈Ck的連通單圈圖,并且

引理3[11]令Δ表示圖G的最大的頂點度,mi表示圖G中與頂點vi鄰接的頂點的度數(shù)的平均值。則有

引理4[7]若兩個二部圖G和H是拉普拉斯同譜圖,則它們所對應的線圖l(G)和l(H)是鄰接同譜的。

引理5[7]任意簡單圖的長度為4的閉合回路數(shù)等于其邊數(shù)的2倍加上長度為2的誘導路數(shù)的4倍再加上8倍的長度為4圈的數(shù)目。

2 主要結果

定理當p為偶數(shù)時,圖G=H(p,2K1,6)由其拉普拉斯譜確定。

證明:假設圖G和圖G′是拉普拉斯譜的,則由引理1可知,圖G′是一個具有p+12個頂點,p+12條邊且含有圈Cp的連通單圈圖。由引理3得

所以Δ≤9。

設ni是圖G中度為i的頂點個數(shù)。由引理1和引理2知

解上述方程組得

n1=35n9-28+n5+4n6+10n7+20n8,

n2=p+138-120n9-4n5-15n6-36n7-70n8,

n3=140n9-168+6n5+20n6+45n7+84n8,

n4=70-56n9-4n5-10n6-20n7-35n8。

由引理2知圖G′含有圈Cp,所以有

由此推出

n1=n5+4n6+10n7+20n8+35n9-28≤12。

由ni≥0(i=2,3,4)可得

n5+4n6+10n7+20n8+35n9≤40,

(1)

4n5+15n6+36n7+70n8+120n9≤p+138,

(2)

6n5+20n6+45n7+84n8+140n9≥168,

(3)

4n5+10n6+20n7+35n8+56n9≤70。

(4)

由(1)×6-(3)得

4n6+15n7+36n8+70n9≤72。

(5)

由(2)×3-(3)×2得

5n6+18n7+42n8+80n9≤p+78。

(6)

由(3)×2-(4)×3得

10n6+30n7+63n8+112n9≥126。

(7)

由(5)×5-(7)×2得

5n7+18n8+42n9≤36。

(8)

因為n9≥0為整數(shù)且p為大于3的任意偶數(shù),所以由(8)得到n9=0,n8≤2.針對n8≤2,分下面3種情況進行討論。

情況1若n8=2,代入(1)可得:n7=n6=n5=0,進而推出n2=p-2,n3=n4=0,n1=12.此種情況成立。

情況2若n8=1,代入(4)可得:n7≤1,若n7=1,代入(7),可推得n6≥3.3,再代入(4)得到矛盾。若n7=0,代入(7),可推得n6≥6.3,同樣代入(4)得到矛盾。所以綜合兩種情況,情況n8=1不成立。

情況3若n8=0,代入(4)可得:n7≤3.5,因為ni(i=1,…,9)是大于等于0的正整數(shù),所以討論如下。

若n7=3,代入(4),可推得n6≤1。若n6=1,代入(4),可推得n5=0,再代入(3)得到矛盾。若n6=0,同n6=1的討論也得到矛盾。所以在n8=0的情況下n7=3這種情形不成立。n7=2的情形討論同n7=3,可以推出也不成立.若n7=1,代入(7),可推得n6≥9.6,同樣代入(4)得到矛盾。n7=0的情形討論同n7=1也可得到矛盾。所以綜合以上討論,可知n8=0的情況也不成立。

綜合以上3種情況,可知只有n8=2的情況成立,此時圖G′的度序列為d(G′)=(82,2p-2,112)。而含有圈Cp且度序列為(82,2p-2,112)的連通單圈圖只能是形如H(p,2K1,6)的圖,但是圖G′的兩個2度點在圈Cp上的位置可能相鄰,也可能不相鄰,所以討論如下:

情況1若圖G′兩個2度點的位置在圈Cp上相鄰,則G′?G。

情況2若圖G′兩個2度點的位置在圈Cp上相鄰不相鄰,因為p為大于3的偶數(shù),所以圖G′和G都是二部圖。由引理4可知圖G′和G的線圖l(G′)和l(G)具有相同的鄰接譜。借助引理1可知線圖l(G′)和l(G)具有相同數(shù)目長度為4的閉回路。再由引理1和引理5可知線圖l(G′)和l(G)中長度為2的誘導路的個數(shù)也是相同的。線圖l(G′)的度序列為(84,712,2p-4),l(G)的度序列為(141,82,712,2p-3),由此推出

得到矛盾,所以此種情況不成立。

綜上所述,圖G′中兩個2度點的位置在圈Cp上相鄰,此種情況G′?G,即當p為偶數(shù)時,圖G=H(p,2K1,6)是由其拉普拉斯譜確定的。

3 結語

本文在一定條件下,借助圖與它的補圖之間的關系和拉普拉斯同譜圖的一些性質(zhì),證明了單圈圖H(p,2K1,6)由它的拉普拉斯譜確定。對于單圈圖H(p,tK1,m)(t>1,m>6)的情形還沒有研究,有興趣的讀者可以繼續(xù)討論下去。