盧鵬麗，王旭柱，陳作漢

(蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅蘭州730050)

本文所涉及的圖都是簡(jiǎn)單無(wú)向圖.設(shè)圖G= (V(G)，E(G))的頂點(diǎn)集和邊集分別為V(G)={v1，v2，…，vn}和E(G)，其中v1，v2，…，vn按頂點(diǎn)的度非遞增排列.設(shè)A(G)=(auv)是圖G的鄰接矩陣，當(dāng)u和v相鄰時(shí)，auv=1，當(dāng)u和v不相鄰時(shí)，auv=0.di= di(G)=dG(vi)是頂點(diǎn)vi的度，D(G)是對(duì)角元素為{d1，d2，…，dn}的n×n對(duì)角矩陣，則矩陣L(G)= D(G)－A(G)稱(chēng)為圖G的Laplacian矩陣.顯然，L(G)是一個(gè)最小特征值為0的半正定對(duì)稱(chēng)矩陣.設(shè)μ1≥μ2≥…≥μn(=0)是L(G)的特征值，它們構(gòu)成了圖G的Laplacian譜.如果2個(gè)圖有相同的Laplacian譜，就說(shuō)他們是Laplacian同譜圖.如果與圖G同Laplacian譜的圖都與圖G同構(gòu)，則稱(chēng)圖G可由它的Laplacian譜確定.

關(guān)于“哪些圖可由它們的譜確定?”這個(gè)問(wèn)題的背景，建議讀者參閱文獻(xiàn)［1－2］，到目前為止，只有少量結(jié)構(gòu)特殊的圖被證明了能由它們的譜確定［1－4］.因此，尋找新的譜確定圖是一個(gè)有趣的問(wèn)題.

文獻(xiàn)［3］證明了lollipop圖(表示為Cn，g，它是在一條頂點(diǎn)數(shù)為n－g的路圖的一個(gè)懸掛點(diǎn)上連接一個(gè)圈Cg得到的圖)能由其Laplacian譜確定.文獻(xiàn)［5］證明了圖H(n;q，n1，n2)(它是在一個(gè)圈Cq的同一個(gè)頂點(diǎn)上懸掛2條路Pn1，Pn2而構(gòu)成的圖，n是它的頂點(diǎn)數(shù))能由其Laplacian譜確定.

本文證明了圖H(n;q，n1，n2，n3)可由其Laplacian譜確定.

1 基本引理

引理1［1］對(duì)于圖G，由其鄰接譜和Laplacian譜可得圖G的下列性質(zhì):

1)頂點(diǎn)數(shù)，

2)邊數(shù)，

3)G是否是正則圖.

由其鄰接譜可得:

4)任意長(zhǎng)度的閉回路數(shù)，

5)圖G是否是二部圖.

由其Laplacian譜可得:

6)分支數(shù)目，

7)生成樹(shù)數(shù)目，

8)頂點(diǎn)的度平方和.

引理2［1］設(shè)N是一個(gè)n×n的對(duì)稱(chēng)矩陣，其特征根為α1≥α2≥…≥αn.N的m階主子矩陣的特征根為α1'≥α2'≥…≥αm'，則αi≥αi'≥αn－m+i，i= 1，2，…，m.

引理3［6］設(shè)A=［aij］是一個(gè)n階方陣，令

是矩陣A第i行元素的絕對(duì)值的和，則

式中:ρ(A)是矩陣A的最大特征值.相似地，對(duì)于矩陣A中列元素的絕對(duì)值的和，該不等式也成立.

引理4［7－8］設(shè)圖 G的頂點(diǎn)集和邊集分別為V(G)≠?和E(G)≠?.則

式中，Δ(G)表示圖G中頂點(diǎn)最大的度，mi表示圖G中與頂點(diǎn)vi鄰接的頂點(diǎn)的度數(shù)的平均值.

本文將方陣B的特征多項(xiàng)式表示為

式中，I是單位陣.特殊地，當(dāng)B=L(G)時(shí)，將φ(L(G))寫(xiě)成φ(G;x)或直接寫(xiě)成φ(G)，稱(chēng)φ(G)為圖G的Laplacian特征多項(xiàng)式.

引理5［5］設(shè)圖G有n個(gè)頂點(diǎn)m條邊，deg(G)=(d1，d2，…，dn)為它的非遞增度序列.則φ(G)的前4個(gè)系數(shù)為

式中:nG(C3)表示圖G中三角圖的數(shù)目.

引理6［4］設(shè)圖G是一個(gè)頂點(diǎn)數(shù)n≥3的連通圖，則μ2≥d2.

這里，用符號(hào)Φ表示一個(gè)森林，它的每個(gè)分支都是一棵樹(shù).用p(Φ)表示森林Φ中各個(gè)分支的頂點(diǎn)數(shù)的乘積.

引理7［9］多項(xiàng)式φ(G)的系數(shù)li可由下式得出:

對(duì)圖G的具有i條邊的所有子森林求和.

設(shè)Pn和Cn分別是具有n個(gè)頂點(diǎn)的路和圈，Bn是從L(Pn+1)中刪除路Pn+1的2個(gè)端點(diǎn)之一對(duì)應(yīng)的行和列后得到的n階矩陣，Hn是從L(Pn+2)中刪除Pn+2的2個(gè)端點(diǎn)對(duì)應(yīng)的行和列后得到的n階矩陣.

引理8［10］設(shè)φ(P0)=0，φ(B0)=1，φ(H0)= 1.則有:

通過(guò)簡(jiǎn)單的計(jì)算便能得到，φ(P1;4)=4.根據(jù)引理8中的遞推公式，可以得到如下結(jié)論.

引理9

設(shè)v是圖G的一個(gè)頂點(diǎn)，令Lv(G)是從L(G)中刪去頂點(diǎn)v對(duì)應(yīng)的行和列后得到的L(G)的主子矩陣.

引理10［11］設(shè)圖G=G1u∶vG2是通過(guò)一條邊連接圖G1的頂點(diǎn)u和圖G2的頂點(diǎn)v得到的圖，則

引理11［5］設(shè)圖G是含有圈Cq的頂點(diǎn)數(shù)為n的連通單圈圖.如果圖G'與圖G同Laplacian譜，則G'是一個(gè)含有圈Cq的頂點(diǎn)數(shù)為n的連通單圈圖，而且:

2 主要結(jié)果

定理1 如果2個(gè)形如H(n;q，n1，n2，n3)的圖同Laplacian譜，則它們必定同構(gòu).

證明 令圖G=H(n;q，n1，n2，n3)(見(jiàn)圖1).設(shè)G'=H(n;q'，n1'，n2'，n3')與圖G同Laplacian譜.根據(jù)引理11，q'=q.則:

圖1 圖H(n;q，n1，n2，n3)Fig.1 The graph H(n;q，n1，n2，n3)

根據(jù)引理7，得到

式中:Φ表示所有的在圖G的圈Cq上刪去2條邊而得到的子森林.

相似地，

將式(3)～(5)代入式(2)，得到

相似地，對(duì)l'n－2，有

因?yàn)閚1+n2+n3=n1'+n2'+n3'，所以，

因?yàn)閘n－2=l'n－2，所以，

應(yīng)用引理10，可以將圖G的Laplacian特征多項(xiàng)式寫(xiě)成如下形式:

其中:

圖G2=H(n－n1;q，n2，n3)，圖G3=Cn－n1－n2，q.

將式(8)、(9)代入式(7)，根據(jù)引理8、9，可得

相似地，對(duì)于圖G'同樣有，

因?yàn)棣?G;4)=φ(G';4)，所以，

聯(lián)立式(6)、(10)，解得

顯然，n1、n2、n3與n1'、n2'、n3'分別是三次方程:

的根.所以圖G與圖G'同構(gòu).

定理2 圖H(n;q，n1，n2，n3)由它的Laplacian譜確定.

證明 令G=H(n;q，n1，n2，n3).設(shè)圖G'與圖G同Laplacian譜.根據(jù)引理11，圖G'是一個(gè)含有圈Cq的連通單圈圖，它有n個(gè)頂點(diǎn)n條邊.設(shè)圖G'由xj'個(gè)度為j的頂點(diǎn)，j=1，2，…，Δ，其中，Δ是圖G'中最大的度.根據(jù)引理4所以，Δ=d1(G')≤5.又max{ri(Lv(G))}=4，其中，i=1，2，…，n－1.根據(jù)引理3，μ1(Lv(G))≤4.

由引理2可得μ1(L(G))≥μ1(Lv(G))≥μ2(L(G))，即μ2(G)≤4.根據(jù)引理6，d2(G')≤μ2(L(G'))≤4，即d2(G')≤4.

因此，圖G'至多有一個(gè)度大于4的頂點(diǎn).所以，由引理1的1)、2)、8)和引理11得到

通過(guò)Maple解方程(11)，得到

現(xiàn)在，考慮下列情況:

1)當(dāng)Δ=1時(shí)，x1'=1，x2'=n，x3'=－6，x4'=4;

2)當(dāng)Δ=2時(shí)，x1'=2，x2'=－1+n，x3'=－6，x4'=4;

3)當(dāng)Δ=3時(shí)，x1'=2，x2'=n，x3'=－7，x4'=4;

4)當(dāng)Δ=4時(shí)，x1'=2，x2'=n，x3'=－6，x4'=3;

5)當(dāng)Δ=5時(shí)，x1'=3，x2'=n－4，x3'=0，x4'=0.

因?yàn)閤i'是非負(fù)整數(shù)，所以Δ=5.

所以，圖G'的形式是H(n;q，n1'，n2'，n3').根據(jù)定理1，圖H(n;q，n1'，n2'，n3')與H(n;q，n1，n2，n3)同構(gòu).

3 結(jié)束語(yǔ)

本文證明了圖H(n;q，n1，n2，n3)可由它的Laplacian譜確定.因?yàn)橐粋€(gè)圖的Laplacian特征值決定它的補(bǔ)圖的 Laplacian特征值［7］，因此，圖H(n;q，n1，n2，n3)的補(bǔ)圖也由它的Laplacian譜確定.

［1］CVETKOVIC M，DOOB M，SACHS H.Spectra of graphs: theory and applications［M］.3rd ed.Heidelberg-Leipzig: Johan Ambrosius Bart Verlag，1995:23-47.

［2］VAN DAM E R，HAEMERS W H.Which graphs are determined by their spectrum?［J］.Linear Algebra Appl，2003，373:241-272.

［3］HAEMERS W H，LIU X G，ZHANG Y P.Spectral characterizations of lollipop graphs［J］.Linear Algebra Appl，2008，428:2415-2423.

［4］LI J S，PAN Y L.A note on the second largest eigenvalue of the Laplacian matrix of a graph［J］.Linear and Multilinear Algebra，2000，48(20):117-121.

［5］LIU X G，WANG S J，ZHANG Y P，et al.On the spectral characterization of some unicyclic graphs［J］.Discrete Mathematics，2011，311(21):2317-2336.

［6］BRUALDI R A，CVETKOVIC D.A combinatorial approach to matrix theory and its applications［M］.Boca Raton: Chapman＆Hall/CRC Press，2009:180.

［7］KELMANS A K，CHELNOKOV V M.A certain polynomial of a graph and graphs with an extremal number of trees［J］.Journal of Combinatorial Theory，Series B，1974，16:197-214.

［8］LI J S，ZHANG X D.On the Laplacian eigenvalues of a graph［J］.Linear Algebra Appl，1998，285:305-307.

［9］BIGGS N L.Algebraic graph theory［M］.2nd ed.Cambridge:Cambridge University Press，1993:47-48.

［10］GUO J M.A conjecture on the algebraic connectivity of connected graphs with fixed girth［J］.Discrete Math，2008，308:5702-5711.

［11］GUO J M.On the second largest Laplacian eigenvalue of trees［J］.Linear Algebra Appl，2005，404:251-261.