兩類雙圈圖的Laplacian譜確定問題

王展青，王力工*，梅若星，翟若男，董占鵬

（西北工業(yè)大學　理學院應用數學系，陜西西安710072）

?

兩類雙圈圖的Laplacian譜確定問題

王展青，王力工*，梅若星，翟若男，董占鵬

（西北工業(yè)大學理學院應用數學系，陜西西安710072）

設G =（V（G），E（G））是一個簡單連通圖，V（G），E（G）分別表示圖G的頂點集和邊集.如果與圖G同Laplacian譜的圖都與G同構，則稱圖G由它的Laplacian譜確定.該文定義了兩類雙圈圖Q（n；n1，n2，···，nt）和B（n；n1，n2），證明了雙圈圖Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3）和雙圈圖B（n；n1，n2）分別由它們的Laplacian譜確定.

Laplacian矩陣；Laplacian特征多項式；Laplacian譜

§1　引　言

本文所考慮的圖都是簡單連通無向圖.雙圈圖是指一個邊數比頂點數多1的簡單連通圖.根據一個n階雙圈圖的雙圈相對位置的不同，可以將n階雙圈圖劃分為三類，分別為An（p，q），Bn，m（p，q）和Cn（p，q），其中:An（p，q）表示其中兩個圈Cp和Cq有且只有一個公共頂點的n階雙圈圖，Bn，m（p，q）表示其中兩個圈Cp和Cq有m（≥2）個公共頂點的n階雙圈圖，Cn（p，q）表示其中兩個圈Cp和Cq沒有公共頂點的n階雙圈圖.設圖G =（V（G），E（G））的頂點集和邊集分別為V（G）= ｛v1，v2，···，vn｝和E（G）.用A（G）表示圖G的鄰接矩陣，di= di（G）= dG（vi）表示頂點vi的度，D（G）= diag（d1，d2，···，dn）表示頂點度對角矩陣. deg（G）=（d1，d2，···，dn）表示圖G的頂點度序列，當頂點度序列中有k個相等的di時，可將這k個di記為dki.矩陣L（G）= D（G）- A（G）為圖G的Laplacian矩陣.多項式?（L（G）；μ）= det（μIn- L（G））= l0μn+ l1μn-1+···+ ln表示圖G的Laplacian特征多項式，In是一個n×n階單位矩陣.下文將?（L（G）；μ）寫成?（G；μ）或直接寫成?（G）.設μ1≥μ2≥···≥μn是L（G）的特征值，它們構成了圖G的Laplacian譜.如果兩個圖有相同的Laplacian譜，就說它們是Laplacian同譜圖.如果與圖G同Laplacian譜的圖都與圖G同構，則稱圖G可由它的Laplacian譜確定.

“哪些圖可由它們的譜確定？”這一典型問題是由G¨unthard和Primas于1956年提出的［1］，它起源于化學，是圖譜理論中一個有趣且困難的問題. 1966年，Fisher在考慮Kac［2］提出的問題“一個人能否聽到鼓聲的形狀”時，研究的正是圖的譜確定問題.研究這個問題的另一動機來自于復雜性理論. 2003年，van Dam和Haemers再次提出這個問題［3］，并受到國內外學者的廣泛關注.尋找具有特殊結構的圖的鄰接譜，Laplacian譜或signless Laplacian譜確定問題是一件非常有意義的事情.這方面好的研究成果見綜述［3-4］和文獻［5-6］.

本文定義了圖Q（n；n1，n2，···，nt），圖B（n；n1，n2）和圖G4，見圖1所示.然后證明了雙圈圖Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3）和雙圈圖B（n；n1，n2）分別由它們的Laplacian譜確定.

圖1　圖Q（n；n1，n2，···，nt），　圖B（n；n1，n2），　圖G4～= K4- e

§2　基本引理

引理2.1［3］對于圖G，由其Laplacian譜可以確定圖G的:

（1）頂點數.

（2）邊數.

（3）分支數數目.

（4）頂點度的平方和.

（5）生成樹的個數.

引理2.2［7-8］設圖G的頂點集和邊集分別為V（G）/=?和E（G）/=?.則有

其中?是圖G的最大的頂點度，mi表示圖G中與頂點vi鄰接的頂點的度數的平均值.

引理2.3［9］多項式?（G）的系數li可由下式得出:

其中Φ表示恰有i個連通分支的生成森林，它的每個分支都是一棵樹，用p（Φ）表示森林Φ中各個分支的頂點數的乘積.

引理2.4［5］圖G有n個頂點，m條邊，deg（G）=（d1，d2，···，dn）為其非遞增的頂點度序列. 則?（L（G）；μ）的前四個系數為

式中nG（C3）表示圖G中三角形的數目.

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

引理2.5［10］設?（P0）= 0，?（B0）= 1，?（H0）= 1.則有:引理2.6［6］如果μ/= 4，且y滿足方程y2-（μ- 2）y + 1 = 0.則有以下結論:

設v是圖G的一個頂點，令Lv（G）是從L（G）中刪去頂點v對應的行和列后得到的L（G）的主子矩陣.

引理2.7［11］設圖G = G1u : vG2是通過一條邊連接圖G1的頂點u和圖G2的頂點v得到的圖，則

?（G）=?（G1）?（G2）-?（G1）?（Lv（G2））-?（G2）?（Lu（G1））.

引理2.8設圖G是含有雙圈G4～= K4- e作為點導出子圖的連通雙圈圖.如果圖G′與圖G同Laplacian譜，則G′是一個含有雙圈G4作為點導出子圖的連通雙圈圖.

證因為圖G和G′同Laplacian譜，由引理2.1知，圖G′與圖G的頂點數，邊數及分支數數目相同，所以圖G′一定為連通的雙圈圖.

設圖G是n階雙圈圖，根據上面結論以及雙圈圖的定義和它的三種分類，則n階雙圈圖G′可能是三類雙圈圖An（p，q），Bn，m（p，q）和Cn（p，q）中的一種，下面證明n階雙圈圖G′不可能是形如An（p，q）或Cn（p，q）的雙圈圖.因為由引理2.1知，圖G和G′的生成樹數目相同.而若圖G′中的兩個圈Cp和Cq（p，q≥3）有且只有一個公共頂點或無公共頂點，就是雙圈圖An（p，q）或Cn（p，q），此時它們的生成樹數目都為pq≥9，這與圖G的生成樹數目為8矛盾.因此n階雙圈圖G′只可能是雙圈圖Bn，m（p，q）（m≥2）.

下面證明n階雙圈圖G′只能是m = 2，p = q = 3的雙圈圖Bn，m（p，q）= Bn，2（3，3）.因為若圖G′是Bn，m（p，q）（m≥2），則它的兩個圈Cp和Cq有m≥2個公共頂點，且有p≥（m + 1），q≥（m + 1），則圖G′的生成樹數目為

因此，上式等號成立當且僅當p = q = 3，m = 2.因此圖G′～= Bn，2（3，3）.

因此，圖G′～= Bn，2（3，3）是一個含有雙圈G4作為點導出子圖的連通雙圈圖.

令q3（G）= 6nG（C3）-Pni=1（di- 2）3.

引理2.9若圖G′與圖G同Laplacian譜，則q3（G）= q3（G′）.

由引理2.1和引理2.4易知，證明過程略.

引理2.10若圖G與圖G′同Laplacian譜，則

由引理2.1易知，證明過程略.

§3　主要結果

定理3.1雙圈圖Q（n；n1）（見圖1）由其Laplacian譜確定.

證G = Q（n；n1）.設圖G′與圖G同Laplacian譜.設圖G′由x′j個度為j的點，j = 1，2，···，△，其中，△是圖G′中最大的度.根據引理2.2，△+ 1≤μ1（G）=μ1（G′）≤6，所以，△= d1（G′）≤5.由引理2.10和引理2.1的（1）可得:

（2）和（3）相加得:

因此，x′5= 0，x′4= 0，1.

（1）x′4= 1.圖G′的度序列為（11，2n-3，31，41）.

（2）x′4= 0.圖G′的度序列為（12，2n-6，34）.

由引理2.8知圖G和G′中均含圖G4（見圖1），所含三角形個數均為2.又由引理2.9，q3（G）= q3（G′），可得圖G′的度序列只可能為（11，2n-3，31，41）.所以圖G′的形式是Q（n；n′1），根據引理2.1，n1= n′1，因此，圖Q（n；n′1）與圖Q（n；n1）同構.

引理3.1如果兩個形如Q（n；n1，n2）（見圖1）的圖同Laplacian譜，則它們必定同構.

證令圖G = Q（n；n1，n2）.設G′= Q（n；n′1，n′2）與圖G同Laplacian譜.根據引理2.1，

根據引理2.3，得到:

式中Φ表示所有在圖G中的G4（見圖1）上刪去三條邊而得到的子森林.

相似的，

將（7），（8）代入（6），得到:

相似的，對l′n-2，有因為，所以

所以，G和G′同構.

定理3.2雙圈圖Q（n；n1，n2）（見圖1）由其Laplacian譜確定.

證令圖G = Q（n；n1，n2）.設圖G′與圖G同Laplacian譜.設圖個度為j的點，j = 1，2，···，△，其中，△是圖G′中最大的度.根據引理2.2，，所以，△= d1（G′）≤5.由引理2.10和引理2.1的（1）可以得到:

（12）和（13）相加得:

因此，x′5= 0，1.

（1）x′5= 1.圖G′的度序列為（12，2n-4，31，51）.

（2）x′5= 0.圖G′的度序列為（13，2n-6，31，42），（14，2n-9，34，41）或（15，2n-12，37）.

由引理2.8知圖G和G′中均含圖G4，所含三角形個數均為2.又由引理2.9，q3（G）= q3（G′），可得圖G′的度序列只可能為（12，2n-4，31，51）.所以圖G′的形式是Q（n；n′1，n′2），根據引理3.1，圖Q（n；n′1，n′2）與圖Q（n；n1，n2）同構.

引理3.2如果兩個形如Q（n；n1，n2，n3）（見圖1）的圖同Laplacian譜，則它們必定同構.

證令圖G = Q（n；n1，n2，n3）.設G′= Q（n；n′1，n′2，n′3）與圖G同Laplacian譜.根據引理2.1，根據引理2.3，得到:

式中Φ表示所有在圖G中的G4上刪去三條邊而得到的子森林.

相似的，

將（17）-（19）代入（16）可得:

類似的，

令G2= G（n - n3；n1，n2），G3= G（n - n2- n3；n1），G4= G（n - n1- n2- n3）.根據引理2.9，

當x /= 4時，根據引理2.6，由Maple計算可得:（26），（27）代入（23），可以得到:

其中，m = n1+ n2+ n3，

因為圖G和圖G′有相同的Laplacian特征多項式，即?（G）=?（G′），所以

不妨設n1≤n2≤n3≤n4，則）和）關于y的最低次冪分別為2n1+ 2和2n′1+ 2.因此n1= n′1.結合（15），（22）可得:因此，n2=，所以G和G′同構.

定理3.3 雙圈圖Q（n；n1，n2，n3）（見圖1）由其Laplacian譜確定.

證令圖G = Q（n；n1，n2，n3）.設圖G′與圖G同Laplacian譜.設圖G′由個度為j的點，j = 1，2，···，△，其中，△是圖G′中最大的度.根據引理2.2，

所以，△= d1（G′）≤6.由引理2.10和引理2.1的（1）可以得到:

（32）和（33）相加得:

因此，x′6= 0，1.

（1）x′6= 1.圖G′的度序列為

（2）x′6= 0.圖G′的度序列為），）），）或

由引理2.8知圖G和G′中均含圖G4，所含三角形個數均為2.又由引理2.9，q3（G）= q3（G′），可得圖G′的度序列只可能為（13，2n-5，31，61）.所以圖G′的形式是Q（n；n′1，n′2，n′3），根據引理3.2，圖Q（n；n′1，n′2，n′3）與圖Q（n；n1，n2，n3）同構.

引理3.3如果兩個形如B（n；n1，n2）（見圖1）的圖同Laplacian譜，則它們必定同構.

證令圖G = B（n；n1，n2）.設G′= B（n；n′1，n′2）與圖G同Laplacian譜.根據引理2.1，

根據引理2.3，得到:

式中Φ表示所有在圖G中的G4上刪去三條邊而得到的子森林.

相似的，

將（42），（43）代入（41）得到:

相似的，對ln-2′有

因為n1+ n2= n′1+ n′2，（-1）n-2ln-2=（-1）n-2l′n-2，所以

不妨設n1≤n2，n′1≤n′2，由（35），（39）可以得到:

所以，G和G′同構.

定理3.4雙圈圖B（n；n1，n2）（見圖1）由其Laplacian譜確定.

證令圖G = B（n；n1，n2）.設圖G′與圖G同Laplacian譜.設圖G′由x′j個度為j的點，j = 1，2，···，△，其中，△是圖G′中最大的度.根據引理2.2，△+ 1≤μ1（G）=μ1（G′）≤6 +，所以，△=≤5.由引理2.10和引理2.1的（1）可以得到:

（42）和（43）相加得:因此，x′5= 0，1.

（1）x′5= 1.圖G′的度序列為（11，2n-2，51）.

（2）x′5= 0.圖G′的度序列為（12，2n-4，42），（13，2n-7，33，41）或（14，2n-10，36）.

由引理2.8知圖G和G′中均含圖G4，所含三角形個數均為2.又由引理2.9，q3（G）= q3（G′），可得圖G′的度序列只可能為（12，2n-4，42）.所以圖G′的形式是B（n；n′1，n′2），根據引理3.3，圖B（n；n′1，n′2）與圖B（n；n1，n2）同構.

致謝衷心感謝審稿人的意見和建議.

［1］G¨unthard H H，Primas H. Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen［J］. Helv Chim Acta，1956，39: 1645-1653.

［2］Kac M. Can one hearing the shape of a drum？［J］. Amer Math Monthly，1966，73: 1-23.

［3］van Dam E R，Haemers W H. Which graphs are determined by their spectrum？［J］. Linear Algebra Appl，2003，373: 241-272.

［4］van Dam E R，Haemers W H. Developments on spectral characterizations of graphs［J］. Discrete Math，2009，309: 576-586.

［5］Liu Xiaogang，Wang Suijie，Zhang Yuanping. On the spectral characterization of some unicyclic graphs［J］. Discrete Math，2011，311: 2317-2336.

［6］Liu Xiaogang，Zhou Sanming. Spectral characterizations of propeller graphs［J］. Electronic J Linear Algebra，2014，27: 19-38.

［7］Kelmens A K，Chelnokov V M. A certain polynomial of a graph and graphs with an extremal number of trees［J］. J Combin Theory，Ser B，1974，16: 197-214.

［8］Li Jiongsheng，Zhang Xiaodong. 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 Jiming. A conjecture on the algebraic connectivity of connected graphs with fixed grith［J］. Discrete Math，2008，308: 5702-5711.

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

MR Subject Classification: 05C50

Two kinds of bicyclic graphs are determined by their Laplacian spectra

WANG Zhan-qing，WANG Li-gong，MEI Ruo-xing，ZHAI Ruo-nan，DONG Zhan-peng
（Department of Applied Mathematics，School of Science，Northwestern Polytechnical University，Xi'an 710072；China）

Let G =（V（G），E（G））be a simple connected graph with vertex V（G）and edge set E（G）. Two graphs are said to be Laplacian cospectral if they have the same Laplacian spectrum. In this paper，two kinds of bicyclic graphs Q（n；n1，n2，···，nt）and B（n；n1，n2）are defined. It is proved that graphs Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3），and B（n；n1，n2）are determined by their Laplacian spectra.

Laplacian matrix；Laplacian characteristic polynomial；Laplacian spectra

O157.5

A

1000-4424（2016）01-0073-10

2015-01-21

2016-01-26

，Email：lgwangmath@163.com

國家自然科學基金（11171273）；國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃（201410699079）