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

盧鵬麗, 劉曉剛

(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050; 2.墨爾本大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，澳大利亞 墨爾本 3010)

?

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

盧鵬麗1, 劉曉剛2

(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050; 2.墨爾本大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，澳大利亞 墨爾本 3010)

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

關(guān)鍵詞：鄰接譜；Laplacian譜；A-同譜圖；L-同譜圖；線圖

1基本引理

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

1) 結(jié)點(diǎn)的個(gè)數(shù)；

2) 邊的條數(shù)。

對(duì)任意圖，由它的鄰接譜可確定：

3) 圖中任意長(zhǎng)度的閉回路的數(shù)目。

對(duì)任意圖，由它的Laplacian譜可確定：

4)圖的組成分支數(shù)目；

5)生成樹的個(gè)數(shù)；

6)結(jié)點(diǎn)度的平方和。

引理2[24]對(duì)任意圖，長(zhǎng)度為4的閉回路的數(shù)目等于2倍的邊數(shù)加上4倍的長(zhǎng)度為2的導(dǎo)出路的數(shù)目，再加上8倍的長(zhǎng)度為4的圈圖的數(shù)目。

原圖G的線圖記為(G)。在線圖(G)中，其結(jié)點(diǎn)相當(dāng)于原圖G的邊，當(dāng)且僅當(dāng)原圖G中的兩條邊有公共結(jié)點(diǎn)時(shí)，線圖(G)中的結(jié)點(diǎn)則為鄰接點(diǎn)。

引理3[25]設(shè)T是有n個(gè)結(jié)點(diǎn)的樹，(T)是它的線圖，則有

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

引理4[26]設(shè)u是圖G的一個(gè)結(jié)點(diǎn)，從圖G中去掉結(jié)點(diǎn)u及其結(jié)點(diǎn)u的關(guān)聯(lián)邊得到子圖G-u，有

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

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

引理7[27-28]設(shè)圖G的結(jié)點(diǎn)集V(G)和邊集E(G)都不為空，有

式中：mi是圖G中所有與結(jié)點(diǎn)vi相鄰的結(jié)點(diǎn)的度的平均值。

引理 8[29]設(shè)圖G是結(jié)點(diǎn)數(shù)大于等于3的連通圖，則有

引理 9[30]設(shè)圖G是結(jié)點(diǎn)數(shù)大于等于4的連通圖，則有

2主要結(jié)論

似雙星樹是恰好有兩個(gè)結(jié)點(diǎn)的度大于2的樹。將路圖Pn的兩個(gè)懸掛點(diǎn)分別與星圖S1,p及S1,q的中心點(diǎn)重合得到的一類似雙星樹表示為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 設(shè)G=H(p,n,q)滿足n≥4且p>q≥2，則

3)μ3(G)<4。

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

3)刪掉Laplacian矩陣L(G)中對(duì)應(yīng)結(jié)點(diǎn)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，假設(shè)圖G′是圖G的L-同譜圖。那么G′也是似雙星樹，并且度序列為

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

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

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

(1)

(2)

(3)

綜合上述三個(gè)等式可以得到

(4)

(5)

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

情形 1q=2或q=3。假設(shè)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矛盾。

經(jīng)上述討論知，圖G′的結(jié)點(diǎn)的最大度d1=p+1，即度為p+1的結(jié)點(diǎn)數(shù)目np+1≥1。

現(xiàn)在假設(shè)np+1≥2，也就是說G′至少存在兩個(gè)結(jié)點(diǎn)的度為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

進(jìn)而可得

(7)

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

情形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。首先從下面四個(gè)方面考慮d1

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

(12)

這與n3≥0矛盾。

情形2.3.2 假設(shè)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?，F(xiàn)有d1=p-1=q+1

情形2.3.3 假設(shè)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假設(shè)d1≤p且d2≤q+3，由(11)式和p≥q+1得

(15)

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

由上述討論，可以得到d1=p+1，即np+1≥1?，F(xiàn)假設(shè)np+1≥2，即圖G′中至少存在2個(gè)度為p+1的結(jié)點(diǎn)。應(yīng)用式(5)得

進(jìn)一步得到

這與q

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

由此得證。

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

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

(16)

簡(jiǎn)化式(16)得

又p>q≥2，0≤a≤q和0≤b≤p。很容易驗(yàn)證

由此得出矛盾。

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

再次假設(shè)與度為q+1的結(jié)點(diǎn)相鄰的懸掛點(diǎn)有q-a個(gè)，與度為p+1的結(jié)點(diǎn)相鄰的懸掛點(diǎn)有p-b個(gè)，其中a和b是滿足0≤a≤q和0≤b≤p的非負(fù)整數(shù)。通過計(jì)算圖G和G′中結(jié)點(diǎn)的個(gè)數(shù)，可以到

即

(17)

(18)

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

結(jié)合命題1和定理1，有以下結(jié)論：

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

由于一個(gè)圖的L譜可以確定它的補(bǔ)圖[32]的L譜，那么由定理2可得出下面的結(jié)論。

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

3結(jié)論

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

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

參考文獻(xiàn)：

[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]. 湖南師范大學(xué): 自然科學(xué)學(xué)報(bào), 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

中圖分類號(hào)：O157.5, O157.6

文獻(xiàn)標(biāo)志碼：A

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

doi:10.11990/jheu.201409027

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11361033).

收稿日期：2014-09-09.網(wǎng)絡(luò)出版日期：2015-12-15.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151215.1030.008.html