一類單圈圖的Laplacian譜刻畫

盧鵬麗，王旭柱，陳作漢

(蘭州理工大學計算機與通信學院，甘肅蘭州730050)

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

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

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

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

1 基本引理

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

1)頂點數(shù)，

2)邊數(shù)，

3)G是否是正則圖.

由其鄰接譜可得:

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

5)圖G是否是二部圖.

由其Laplacian譜可得:

6)分支數(shù)目，

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

8)頂點的度平方和.

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

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

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

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

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

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

本文將方陣B的特征多項式表示為

式中，I是單位陣.特殊地，當B=L(G)時，將φ(L(G))寫成φ(G;x)或直接寫成φ(G)，稱φ(G)為圖G的Laplacian特征多項式.

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

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

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

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

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

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

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

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

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

引理9

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

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

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

2 主要結(jié)果

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

證明 令圖G=H(n;q，n1，n2，n3)(見圖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)，得到

相似地，對l'n－2，有

因為n1+n2+n3=n1'+n2'+n3'，所以，

因為ln－2=l'n－2，所以，

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

其中:

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

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

相似地，對于圖G'同樣有，

因為φ(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'是一個含有圈Cq的連通單圈圖，它有n個頂點n條邊.設(shè)圖G'由xj'個度為j的頂點，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'至多有一個度大于4的頂點.所以，由引理1的1)、2)、8)和引理11得到

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

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

1)當Δ=1時，x1'=1，x2'=n，x3'=－6，x4'=4;

2)當Δ=2時，x1'=2，x2'=－1+n，x3'=－6，x4'=4;

3)當Δ=3時，x1'=2，x2'=n，x3'=－7，x4'=4;

4)當Δ=4時，x1'=2，x2'=n，x3'=－6，x4'=3;

5)當Δ=5時，x1'=3，x2'=n－4，x3'=0，x4'=0.

因為xi'是非負整數(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é)束語

本文證明了圖H(n;q，n1，n2，n3)可由它的Laplacian譜確定.因為一個圖的Laplacian特征值決定它的補圖的 Laplacian特征值［7］，因此，圖H(n;q，n1，n2，n3)的補圖也由它的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.