程霄

（新疆農(nóng)業(yè)大學(xué) 數(shù)理學(xué)院，新疆 烏魯木齊 830052）

關(guān)于似星樹(shù)擬拉普拉斯譜的性質(zhì)探討

程霄

（新疆農(nóng)業(yè)大學(xué) 數(shù)理學(xué)院，新疆 烏魯木齊 830052）

利用似星樹(shù)的簡(jiǎn)單性質(zhì)，結(jié)合偶圖的Laplacian譜和擬拉普拉斯譜的關(guān)系，得到了擬拉普拉斯同譜的似星樹(shù)同構(gòu)的性質(zhì).進(jìn)一步，通過(guò)矩陣的交錯(cuò)理論，結(jié)合圖操作方法，得到了似星樹(shù)擬拉普拉斯譜的另一個(gè)性質(zhì).最后，根據(jù)其鄰接譜半徑的界，得到了似星樹(shù)的擬拉譜拉斯譜半徑的一個(gè)上界.

擬拉普拉斯矩陣特征值；似星樹(shù)；譜半徑；譜寬度

圖譜理論是代數(shù)圖論的重要研究領(lǐng)域.其中，圖的擬拉普拉斯譜問(wèn)題在微分方程問(wèn)題，矩陣?yán)碚?，量子化學(xué)、生物學(xué)以及復(fù)雜網(wǎng)絡(luò)問(wèn)題中有重要的應(yīng)用，是目前研究的活躍問(wèn)題.

本文討論的圖，均為簡(jiǎn)單無(wú)向圖（不包括環(huán)和平行邊），未定義的概念在文［1］中都可以找到.設(shè)G=（V，E）是n階圖，其頂點(diǎn)集為V，點(diǎn)集為E.分別記D（G）=diag（du：u∈V）和A（G）= （auv）表示圖的度矩陣和鄰接矩陣.其中，du是頂點(diǎn)的度；當(dāng)uv相鄰時(shí)，auv=1；否則，auv=0；鄰接矩陣的特征值記為λ1≥λ2≥…≥λn.圖G的Laplacian矩陣定義為L(zhǎng)（G）=D（G）-A（G），其特征多項(xiàng)式為L(zhǎng)G（x）.由于L（G）是一個(gè)實(shí)對(duì)稱(chēng)半正定的奇異矩陣，故設(shè)其特征值為：μ1≥μ2≥…≥μn=0.圖的擬拉普拉斯（signlessLaplacian）矩陣Q（G）=D（G）+A（G），其特征多項(xiàng)式為QG（x）.由于A（G）是一個(gè)實(shí)對(duì)稱(chēng)的、半正定的非負(fù)矩陣，則設(shè)其特征值為q1≥q2≥…≥qn≥0.

圖G的鄰接矩陣特征值、Laplacian矩陣特征值和擬拉普拉斯矩陣特征值都是圖的不變量.由于后兩個(gè)矩陣都加入了頂點(diǎn)的度，所以其特征值更能反映圖的性質(zhì).關(guān)于圖的譜半徑問(wèn)題以及譜確定問(wèn)題，一直以來(lái)都是前沿?zé)狳c(diǎn)問(wèn)題.

似星樹(shù)（starlike tree）是一類(lèi)特殊的樹(shù)圖，即只有一個(gè)頂點(diǎn)的度數(shù)大于2的樹(shù).關(guān)于其鄰接譜半徑問(wèn)題以及Laplacian譜確定問(wèn)題研究，已經(jīng)取得了大量的研究成果［3-5］.不過(guò)關(guān)于其擬拉普拉斯譜的性質(zhì)的研究較少.

本文在已有的研究基礎(chǔ)上，通過(guò)矩陣?yán)碚?、圖論的相關(guān)知識(shí)，結(jié)合圖操作等方法，進(jìn)一步對(duì)似星樹(shù)的擬拉普拉斯特征值，譜半徑，譜寬度等問(wèn)題進(jìn)行探討，得到了一些結(jié)論.

1 基本理論

引理1［6］設(shè)n×n矩陣M和H，則下面的關(guān)系是等價(jià)的：

（1）M和H具有相同的譜；

（2）M和H具有相同的特征多項(xiàng)式；

引理2［7］偶圖的擬拉普拉斯矩陣和Laplacian矩陣具有相同的特征多項(xiàng)式，即QG（x）=LG（x）

很多文獻(xiàn)提到過(guò)此定理，但沒(méi)給出詳細(xì)證明，其過(guò)程如下.

證明 設(shè)G是偶圖，兩部集的階數(shù)為n1，n2.結(jié)合分塊矩陣的理論，頂點(diǎn)按一定的順序標(biāo)號(hào)，G的鄰接矩陣A可寫(xiě)成

接下來(lái)，對(duì)LG（x）的前n1行和n1列分別都乘以-1，那正好得到QG（x），由此得證.

為了證明似星樹(shù)的擬拉普拉斯譜的性質(zhì)，需要引入矩陣?yán)碚撝械慕诲e(cuò)原則.考慮兩個(gè)實(shí)數(shù)序列：

如果αi≥βi≥αn-m+i（i=1，2，…，m），則稱(chēng)第二個(gè)序列交錯(cuò)于第一個(gè)序列.

引理3［2］設(shè)S是一個(gè)n×m的實(shí)矩陣，滿(mǎn)足STS=I.同時(shí)，設(shè)A是一個(gè)n階實(shí)對(duì)稱(chēng)矩陣，且特征值為α1≥α2≥…≥αn.定義B=STAS，其特征值為：β1≥β2≥…≥βm，那么B的特征值序列交錯(cuò)于A的特征值序列.

在上述定理中，若令S=［I0］T，那么B就是A的一個(gè)主子陣，則有：

引理4［2］設(shè)B是對(duì)稱(chēng)矩陣A的主子陣，則B的特征值序列交錯(cuò)于A的特征值序列.

利用此引理，就能得到圖譜理論中相應(yīng)的交錯(cuò)定理.

引理5［8］（邊交錯(cuò)定理）設(shè)圖G有n個(gè)頂點(diǎn)，m條邊.且e∈E（G），并設(shè)G的擬拉普拉斯特征值和G-e的擬拉普拉斯特征值分別為：q1≥q2≥…≥qn，s1≥s2≥…≥sn，那么：

0≤sn≤qn≤…≤s2≤q2≤s1≤q1

文獻(xiàn)［9］中，利用此引理，同時(shí)結(jié)合矩陣?yán)碚撝械腤ely's不等式和Cquchy交錯(cuò)定理，得到了關(guān)于擬拉普拉斯特征值的點(diǎn)交錯(cuò)定理.

引理6［9］（點(diǎn)交錯(cuò)定理）設(shè)圖G為n階圖，頂點(diǎn)集為V （G），且v∈V（G），設(shè)G的擬拉普拉斯特征值和G-v的擬拉普拉斯特征值分別為q1（G）和qi（G-v），其中i=1，2，…，n.那么：

其中，右邊的等號(hào)成立，當(dāng)且僅當(dāng)v是孤立點(diǎn).

為了討論似星樹(shù)的擬拉普拉斯譜半徑問(wèn)題，需要引入以下定理：

引理7［8］若n階圖G至少有一條邊，設(shè)其最大度為Δ，那么：

若G是連通的，則當(dāng)且僅當(dāng)G是偶圖，有第一個(gè)等號(hào)成立；當(dāng)且僅當(dāng)=n-1.有第二個(gè)等號(hào)成立.

引理8［10］設(shè)G為n階圖，則有

其中，λ1是圖G的鄰接譜半徑；當(dāng)且僅當(dāng)G是正則的，等號(hào)成立.

2 主要結(jié)果

定義1［11］只有一個(gè)頂點(diǎn)的度數(shù)大于2的樹(shù)，稱(chēng)為似星樹(shù).記為S（n1，n2，…，nk），其中n1，n2，…，nk是正整數(shù)，n1≥n2≥…≥nk≥1，且頂點(diǎn)最大度為k（k≥3）.

定理1 如果兩棵似星樹(shù)S（n1，n2，…，nk）和S（m1，m2，…，mk）是擬拉普拉斯同譜圖，那么它們一定是同構(gòu)的.

證明 文獻(xiàn)［12］中通過(guò)似星樹(shù)的線(xiàn)圖的性質(zhì)，證明了只要兩棵似星樹(shù)是同譜的，則一定也是同構(gòu)的.樹(shù)是一類(lèi)特殊的偶圖，由引理2可知，偶圖的擬拉普拉斯譜等于其Laplacian譜，那么結(jié)論得證.

定理2 似星樹(shù)最多只有一個(gè)擬拉普拉斯特征值不小于5.

證明 由似星樹(shù)的定義，不妨設(shè)頂點(diǎn)v的度數(shù)為k，那么顯然它有下面的性質(zhì)：

因此，q2（S）-1≤q1（S-v）≤q1（S），又因?yàn)閝1（S-v）＜4，那么顯然q2（S）＜5.結(jié)論得證.

定理3 設(shè)q1是Starlike樹(shù)S（n1，n2，…，nk）的Q-譜半徑，且Δ是其最大度，那么對(duì)任意的n1≥n2≥…≥nk≥1，都有：

其中，n=n1+n2+…+nk+1，下界的等號(hào)成立，當(dāng)且僅當(dāng)n1=n2=…=nk=1，即G是星圖Sn.

證明 一方面，由邊交錯(cuò)定理和引理7易得q1的下界.當(dāng)且僅當(dāng)n1=n2=…=nk=1時(shí)，G是星圖Sn，q1取得最小值.另一方面，由引理8可知，q1≤λ1+Δ，只要根據(jù)似星樹(shù)的鄰接譜半徑的界，便可找到q1的上界，在文獻(xiàn)［11］中，證明了似星樹(shù)S（n1，n2，…，nk）的鄰接譜半徑的一個(gè)界，即對(duì)任意的n1≥n2≥…≥nk≥1，都有：

由似星樹(shù)的定義可知，k是該圖的最大度，也即

綜上所述，結(jié)論得證.

對(duì)于擬拉普拉斯譜寬度的研究也是一個(gè)方向，通過(guò)上面的定理易得下面的結(jié)論.

推論 設(shè)SQ（S）是似星樹(shù)S（n1，n2，…，nk）的擬拉普拉斯譜寬度（即q1-qn）.且Δ是其最大度，那么對(duì)任意的n1≥n2≥…≥nk≥1，都有：

其中，n=n1+n2+…+nk+1，下界的等號(hào)成立，當(dāng)且僅當(dāng)n1=n2=…=nk=1，即G是星圖Sn.

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

針對(duì)一類(lèi)特殊的圖——似星樹(shù)，得到了其部分?jǐn)M拉普拉斯譜的性質(zhì).關(guān)于似星樹(shù)的擬拉普拉斯譜的研究，還值得深入討論，譜確定問(wèn)題和頂點(diǎn)連通度問(wèn)題仍是重要研究方向［13-14］.

〔1〕Bondy JA，Murty U S R.Graph theory with applications［M］.New York：Macmillan，1976.

〔2〕A.E.Brouwer，W.H.Haemers.Spectra of graphs［M］. Springer Verlag，2011.

〔3〕姚瑤，徐美進(jìn)，楊文杰，等.最大度為4的似星樹(shù)的譜半徑［J］.遼寧工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，34（01）：67-70.

〔4〕沈小玲.關(guān)于圖的譜確定問(wèn)題［D］.長(zhǎng)沙：湖南師范大學(xué)，2005.

〔5〕姚瑤.一類(lèi)似星樹(shù)的譜半徑問(wèn)題研究［D］.錦州：遼寧工業(yè)大學(xué)，2014.

〔6〕VANDRE，HAEMERSH W.Whichgraphsare determinedby their spectrum ［J］.Linear Algebra Appl.，2003，373：241-272.

〔7〕D.Cvetkovic，P.Rowlinson，S.K.Simic，Signless Laplacians of finite graphs［J］.Linear AlgebraAppl.，2007，423（1）：155-171.

〔8〕D.Cvetkovic，P.Rowlinson，S.K.Simic.Eigenvalue bounds for the signless Laplacian ［J］.Publ.Inst.Math（Beograd），2007，81（95）：11-27.

〔9〕J.F Wang，F(xiàn).Belardo.A note on the signless Laplacian eigenvalues of graphs ［J］. Linear Algebra and its Applications，2011，435：2585-2590.

〔10〕P.Hansen，C.Lucas，Bounds and conjectures for the signless Laplacian indexof graphs［J］.Linear Algebra and itsApplications，2010，432：3319-3336.

〔11〕M.Lepovic，I.gutman.Some Spectral Properties of Stralike trees［J］.Bull.Acad.Serbe Sci.Arts，Cl.Sci.Math. Natur.，Sci.Math，2001，137（33）：99-105.

〔12〕M.Lepovic.Some results on Starlike trees and Sunlike graphs［J］.J.Appl.Math.&Computing，2003 11（1-2）：109-123.

〔13〕C.J.Bu，J.Zhou，Starlike treeswhose maximum degree exceed4 are determined by their Q-spectra［J］. Linear Algebra and itsAppli-cations，2012，436：143-151.

〔14〕S.N.Qiao.Thestarlike treeswith maximum and minimum secondorder connectivity index［J］.J Appl. Math Comput 2012（39）：523-532.

O157.5

A

1673-260X（2015）05-0004-02