似雙星樹H(p,n,q)由Laplacian譜刻畫

盧鵬麗, 劉曉剛

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050; 2.墨爾本大學 數學與統計學院，澳大利亞 墨爾本 3010)

?

似雙星樹H(p,n,q)由Laplacian譜刻畫

盧鵬麗1, 劉曉剛2

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050; 2.墨爾本大學 數學與統計學院，澳大利亞 墨爾本 3010)

摘要：似雙星樹是恰好有兩個結點的度大于2的樹。用H(p,n,q)表示將路圖Pn的兩個懸掛點分別與星圖S(1,p)及S(1,q)的中心點重合所得到的一類似雙星樹。首先得到了頂點的度序列，然后由譜性質證明了似雙星樹H(p,n,q)由Laplacian譜確定，擴大了譜確定圖的范圍。

關鍵詞：鄰接譜；Laplacian譜；A-同譜圖；L-同譜圖；線圖

1基本引理

引理1[13-23]對任意圖，由它的鄰接譜或Laplacian譜可確定：

1) 結點的個數；

2) 邊的條數。

對任意圖，由它的鄰接譜可確定：

3) 圖中任意長度的閉回路的數目。

對任意圖，由它的Laplacian譜可確定：

4)圖的組成分支數目；

5)生成樹的個數；

6)結點度的平方和。

引理2[24]對任意圖，長度為4的閉回路的數目等于2倍的邊數加上4倍的長度為2的導出路的數目，再加上8倍的長度為4的圈圖的數目。

原圖G的線圖記為(G)。在線圖(G)中，其結點相當于原圖G的邊，當且僅當原圖G中的兩條邊有公共結點時，線圖(G)中的結點則為鄰接點。

引理3[25]設T是有n個結點的樹，(T)是它的線圖，則有

式中：i=1,2,…,n-1。

引理4[26]設u是圖G的一個結點，從圖G中去掉結點u及其結點u的關聯邊得到子圖G-u，有

引理5[2]設e是圖G的一條邊，從圖G中去掉邊e得到子圖G′=G-e，有

式中：i=1,2,…,m。

引理7[27-28]設圖G的結點集V(G)和邊集E(G)都不為空，有

式中：mi是圖G中所有與結點vi相鄰的結點的度的平均值。

引理 8[29]設圖G是結點數大于等于3的連通圖，則有

引理 9[30]設圖G是結點數大于等于4的連通圖，則有

2主要結論

似雙星樹是恰好有兩個結點的度大于2的樹。將路圖Pn的兩個懸掛點分別與星圖S1,p及S1,q的中心點重合得到的一類似雙星樹表示為H(p,n,q)，如圖1所示，其中p≥q≥1。

圖1　似雙星樹H(p,n,q)Fig.1　The double starlike treeH(p,n,q)

命題1 1) 若n=1，則H(p,n,q)?K1,p+q且是由Laplacian譜確定的[7]。

2)若n=2或n=3，則H(p,n,q)是由Laplacian譜確定的[31]。

3)若p=q=1，則H(1,n,1)?Pn+2且是由Laplacian譜確定的[3]。

4)若p>q=1，則H(p,n,1)是似星樹且是由Laplacian譜確定的[7]。

5)若p=q≥2，則H(p,n,q)?Hn(p,p)且是由Laplacian譜確定的[10]。

由命題1知，只需考慮似雙星樹H(p,n,q)滿足n≥4且p>q≥2是否由Laplacian譜確定即可。下面，首先給出似雙星圖的最大特征根，次大特征根及第三大特征根的界值。

引理10 設G=H(p,n,q)滿足n≥4且p>q≥2，則

3)μ3(G)<4。

證明：1)由引理7，通過簡單的計算即可得到最大特征根的界值。

3)刪掉Laplacian矩陣L(G)中對應結點u和v的行和列得到(p+n+q-2)×(p+n+q-2)維的主子陣Muv。顯然，Muv的最大特征根小于4。由引理6得μ3(G)<4。

引理11 圖G=H(p,n,q)滿足n≥4且p>q≥2，假設圖G′是圖G的L-同譜圖。那么G′也是似雙星樹，并且度序列為

證明：由引理1的1)、 2) 、3)和4)知，G′為有n+p+q個結點，n+p+q-1條邊的樹。設(d1,d2,…,dn+p+q)是圖G′的非遞增度序列，ni表示圖G′中度為i的結點的個數，其中i=1,2,…,d1。

由引理9和引理10的3)可得d3≤μ3(G′)+1=μ3(G)+1<5，進而得d3≤4。

另一方面，由引理1的1)、2)、6)可以得到如下的等式：

(1)

(2)

(3)

綜合上述三個等式可以得到

(4)

(5)

上面已經證得d1≤p+1，d2≤q+3和d3≤4。下面分兩種情況確定圖G′的度序列。

情形 1q=2或q=3。假設d1

(6)

如果q=2，那么就有p≥3。把q=2代入式(6)可以得到p2-3p+6≤0，這與p≥3矛盾。

如果q=3，那么就有p≥4。把q=3代入式(6)可以得到p2-7p+24≤0，這與p≥4矛盾。

經上述討論知，圖G′的結點的最大度d1=p+1，即度為p+1的結點數目np+1≥1。

現在假設np+1≥2，也就是說G′至少存在兩個結點的度為p+1。有式(5)可得

如果q=2，由式(5)可得n3=1和ni=0，其中i=4,5,…,p。由式(1)、(2)可得n2=n-2和n1=p+2。由此圖G′的度序列為

p3+q3-3p2-3q2+2p+2q

進而可得

(7)

已證得d3≤4， 也就是說，圖G′中至多存在兩個度大于4的結點，下面從三個方面考慮這個問題。

情形2.1d1=4且d2≤4。由式(7)可得

(8)

把式(8)代入式(4)可得

這與n3≥0矛盾。

情形2.2d1>4且d2=4。由式(7)可得

(9)

把式(9)代入式(4)可得

由d1≤p+1和q≥4可得n3<0，這也與n3≥0矛盾。

情形2.3d1>4且d2>4。由式(7)可得

(10)

把式(10)代入式(4)可得

(11)

已證得了d1≤p+1和d2≤q+3。首先從下面四個方面考慮d1

情形2.3.1 假設d1=p且d2=q+3，由式(10)和(11)可得

(12)

這與n3≥0矛盾。

情形2.3.2 假設d1=p-1且d2=q+3，由式(10)和(11)可得

n3=-3p2+14p-16+3q2-2q=

(13)

由n4≥0得p≥q+2。將p≥q+2代入n3中可得n3≤-q(3q-2)+3q2-2q=0，由此可得p=q+2且n3=n4=0。現有d1=p-1=q+1

情形2.3.3 假設d1≤p-2且d2=q+3，有q+3=d2≤d1≤p-2，即p≥q+5。將d1≤p-2和d2=q+3代入(11)式得

(14)

這也與n3≥0矛盾。

情形2.3.4假設d1≤p且d2≤q+3，由(11)式和p≥q+1得

(15)

由n3=0，得出d1=p，d2=q+2和p=q+1。這時有d1=p=q+1

由上述討論，可以得到d1=p+1，即np+1≥1。現假設np+1≥2，即圖G′中至少存在2個度為p+1的結點。應用式(5)得

進一步得到

這與q

由q≥4，再聯合式(10)和(11)得出d2=q+1。由式(5)得，當i=3,4,…,q,q+2,…,p時ni=0。由式(1)和(2)得n1=p+q和n2=n-2，因此得

由此得證。

定理1設圖G=H(p,n,q)滿足n≥4且p>q≥2，則G由Laplacian譜確定的。

另一方面，容易得到圖G的線圖(G)的度序列

(16)

簡化式(16)得

又p>q≥2，0≤a≤q和0≤b≤p。很容易驗證

由此得出矛盾。

圖2　G′圖Fig.2　The graph G′

再次假設與度為q+1的結點相鄰的懸掛點有q-a個，與度為p+1的結點相鄰的懸掛點有p-b個，其中a和b是滿足0≤a≤q和0≤b≤p的非負整數。通過計算圖G和G′中結點的個數，可以到

即

(17)

(18)

簡化式(18)得a(q-1)+b(p-1)=0。于是可得a=0和b=0，把a=0和b=0代入式(14)得l1=n。由此可得圖G′同構于圖G。證明結束。

結合命題1和定理1，有以下結論：

定理2 所有的似雙星樹H(p,n,q)都是由Laplacian譜確定的。

由于一個圖的L譜可以確定它的補圖[32]的L譜，那么由定理2可得出下面的結論。

推論 1 任意似雙星樹H(p,n,q)的補圖都是由Laplacian譜確定的。

3結論

1)當p=q時，即圖H(p,n,p)是由Laplacian譜確定的。

2)當p≠q時，問題的關鍵點是確定圖的度序列deg(G′)，其中圖G′與圖H(p,n,q)是L-同譜圖。本文在引理3中解決了這個問題，并證明了所有似雙星樹H(p,n,q)是由Laplacian譜確定的，得到了這個問題的完整解決。

參考文獻：

[1]GüNTHARD H H, PRIMAS H. Zusammenhang von Graphentheorie und Mo-Theorie von Molekeln mit Systemen konjugierter Bindungen[J]. Helvetica Chimica Acta, 1956, 39(6): 1645-1653.

[2]CVETKOVICD, ROWLINSON P, SIMIC S. An introduction to the theory of graph spectra[M]. Cambridge: Cambridge University Press, 2010: 77-89.

[3]VAN DAM E R, HAEMERS W H. Which graphs are determined by their spectrum?[J]. Linear Algebra and its Applications, 2003, 373: 241-272.

[4]AN DAM E R, HAEMERS W H. Developments on spectral characterizations of graphs[J]. Discrete Mathematics, 2009, 309(3): 576-586.

[5]SHEN Xiaoling, HOU Yaoping, ZHANG Yuanping. Graph Zn and some graphs related to Zn are determined by their spectrum[J]. Linear Algebra and its Applications, 2005, 404: 58-68.

[6]WANG Wei, XU Chengxian. Note: the t-shape tree is determined by its Laplacian spectrum[J]. Linear Algebra and its Applications, 2006, 419(1): 78-81.

[7]OMIDI G R, TAJBAKHSH K. Starlike trees are determined by their Laplacian spectrum[J]. Linear Algebra and its Applications, 2007, 422(2/3): 654-658.

[8]BOULET R. The centipede is determined by its Laplacian spectrum[J]. Comptes Rendus Mathematique, 2008, 346(13/14): 711-716.

[9]STANIC Z. On determination of caterpillars with four terminal vertices by their Laplacian spectrum[J]. Linear Algebra and its Applications, 2009, 431(11): 2035-2048.

[10]LIU Xiaogang, ZHANG Yuanping, LU Pengli. One special double starlike graph is determined by its Laplacian spectrum[J]. Applied Mathematics Letters, 2009, 22(4): 435-438.

[11]BU Changjiang, ZHOU Jiang, LI Hongbo. Spectral determination of some chemical graphs[J]. Filomat, 2012, 26(6): 1123-1131.

[12]AALIPOUR G, AKBARI S, SHAJARI N. Laplacian spectral characterization of two families of trees[J]. Linear and Multilinear Algebra, 2014, 62(7): 965-977.

[13]BOULET R, JOUVE B. The lollipop graph is determined by its spectrum[J]. The Electronic Journal of Combinatorics, 2008, 15(1): 74.

[14]BOULET R. Spectral characterizations of sun graphs and broken sun graphs[J]. Discrete Mathematics and Theoretical Computer Science, 2009, 11(2): 149-160.

[15]CVETKOVIC D M, DOOB M, SACHS H. Spectra of graphs: theory and applications[M]. New York, San Francisco: Academic Press, 1980: 50-53.

[16]HAEMERS W H, LIU Xiaogang, ZHANG Yuanping. Spectral characterizations of lollipop graphs[J]. Linear Algebra and its Applications, 2008, 428(11/12): 2415-2423.

[17]LIU Xiaogang, WANG Suijie. Laplacian spectral characterization of some graph products[J]. Linear Algebra and its Applications, 2012, 437(7): 1749-1759.

[18]LIU Muhuo, LIU Bolian. Some results on the Laplacian spectrum[J]. Computers & Mathematics with Applications, 2010, 59(11): 3612-3616.

[19]LU Pengli, LIU Xiaogang, YUAN Zhanting, et al. Spectral characterizations of sandglass graphs[J]. Applied Mathematics Letters, 2009, 22(8): 1225-1230.

[20]MIRZAKHAH M, KIANI D. The sun graph is determined by its signless Laplacian spectrum[J]. Electronic Journal of Linear Algebra, 2010, 20: 610-620.

[21]WANG Jianfeng, HUANG Qingxiang, BELARDO F, et al. On the spectral characterizations of ∞-graphs[J]. Discrete Mathematics, 2010, 310(13/14): 1845-1855.

[22]ZHOU Jiang, BU Changjiang. Laplacian spectral characterizaiton of some graphs obtained by product operation[J]. Discrete Mathematics, 2012, 312(10): 1591-1595.

[23]SILVA OLIVEIRA C, DE ABREU N M M, JURKIEWILZ S. The characteristic polynomial of the Laplacian of graphs in (a, b)-linear classes[J]. Linear Algebra and its Applications, 2012, 356(1/3): 113-121.

[24]CVETKOVIC D, ROWLINSON P. Spectra of unicyclic graphs[J]. Graphs and Combinatorics,1987, 3(1): 7-23.

[25]GUTMAN I, GINEITYTE V, LEPOVIC M, et al. The high-energy band in the photoelectron spectrum of alkaners and its dependence on molecular structure[J]. Journal of the Serbian Chemical Society, 1999, 64(11): 673-680.

[26]LOTKER Z. Note on deleting a vertex and weak interlacing of the Laplacian spectrum[J]. Electronic Journal of Linear Algebra, 2007, 16(1): 68-72.

[27]KELMANS A K, CHELNOKOV V M. A certain polynomial of a graph and graphs with an extremal numbers of trees[J]. Journal of Combinatorial Theory, Series B, 1974, 16(3): 197-214.

[28]LI Jiongsheng, ZHANG Xiaodong. On the Laplacian eigenvalues of a graph[J]. Linear Algebra and its Applications, 1998, 285(1/3): 305-307.

[29]LI Jiongsheng, PAN Yongliang. A note on the second largest eigenvalue of the Laplacian matrix of a graph[J]. Linear and Multilinear Algebra, 2000, 48(2): 117-121.

[30]GUO Jiming. On the third largest Laplacian eigenvalue of a graph[J]. Linear and Multilinear Algebra, 2007, 55(1): 93-102.

[31]沈小玲, 侯耀平. 一些由它的Laplacian譜確定的樹[J]. 湖南師范大學: 自然科學學報, 2006, 29(1): 21-24, 46.

SHEN Xiaoling, HOU Yaoping. Some trees are determined by their Laplacian spectra[J]. Journal of Natural Science of Hunan Normal University, 2006, 29(1): 21-24, 46.

Double starlike treeH(p,n,q) determined by Laplacian spectrum

LU Pengli1，LIU Xiaogang2

(1. School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China; 2. Department of Mathematics and Statistics, The University of Melbourne, Melbourne 3010, Australia)

Abstract：A tree is called double starlike if it has exactly two vertices of degree greater than two. Let H(p,n,q) denote a class of double starlike tree obtained from two stars S(1,p) and S(1,q) by identifying the center of S(1,p)with one end of Pn and the center of S(1,q) with the other end of Pn. First, we get the degree sequence of vertices. Then, by using spectral properties, it is proved that all double starlike trees H(p,n,q) are determined by their Laplacian spectra, which enlarges the scope of graphs determined by their spectra.

Keywords：adjacency spectrum; Laplacian spectrum; A-cospectral graphs; L-cospectral graphs; line graph

中圖分類號：O157.5, O157.6

文獻標志碼：A

文章編號：1006-7043(2016)02-0242-06

doi:10.11990/jheu.201409027

作者簡介：盧鵬麗(1973-)， 女，教授.通信作者：盧鵬麗，E-mail：lupengli88@163.com.

基金項目：國家自然科學基金資助項目(11361033).

收稿日期：2014-09-09.網絡出版日期：2015-12-15.

網絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151215.1030.008.html