按Laplace譜半徑對(duì)一些偶單圈圖的排序

張 海 霞

( 1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024;2.太原科技大學(xué) 數(shù)學(xué)系, 山西 太原 030024 )

?

按Laplace譜半徑對(duì)一些偶單圈圖的排序

張 海 霞*1,2

( 1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024;2.太原科技大學(xué) 數(shù)學(xué)系, 山西 太原 030024 )

單圈圖；最大Laplace特征值；排序

0 引 言

設(shè)G是n階連通簡(jiǎn)單圖,其頂點(diǎn)集為V(G)={v1,v2,…,vn},邊集為E(G)={e1,e2,…,en}．G的階數(shù)是指G的頂點(diǎn)個(gè)數(shù)．G的Laplace矩陣定義為L(zhǎng)(G)=D(G)-A(G),其中A(G)和D(G)分別為G的鄰接矩陣和度對(duì)角矩陣．G的Laplace特征多項(xiàng)式為Φ(G)=det(xI-L(G)),它的根稱為G的Laplace特征值．既然L(G)是半正定的實(shí)對(duì)稱矩陣,其所有的特征值都是實(shí)數(shù),不妨記為μ1(G)≥…≥μn(G)=0,其中μ1(G)也稱為G的Laplace譜半徑．

圖的Laplace特征值的研究是非?；钴S的研究課題,已經(jīng)有許多結(jié)果[1-5],它的研究不僅對(duì)圖論本身有意義,而且對(duì)其他學(xué)科,例如物理、化學(xué)、生物也有非常重大的意義,因而越來(lái)越受到人們的關(guān)注[4-7]．

單圈圖是邊數(shù)等于頂點(diǎn)數(shù)的簡(jiǎn)單連通圖,它可以看成是樹(shù)在不相鄰的兩個(gè)頂點(diǎn)間連一條邊得到的．如果單圈圖的圈長(zhǎng)為偶數(shù), 也稱單圈圖為偶單圈圖．單圈圖的鄰接譜和Laplace譜的研究已有許多[8-9]．而對(duì)于階數(shù)和圈長(zhǎng)固定的單圈圖的Laplace譜半徑的最小值問(wèn)題仍未考慮．這里先考慮一些特殊的偶單圈圖的Laplace譜半徑的最小值問(wèn)題．

1 用到的引理

引理1[11]記Dn是n階矩陣,它是從路Pn+2對(duì)應(yīng)的L(Pn+2)(n≥1)中刪掉兩個(gè)懸掛點(diǎn)所對(duì)應(yīng)的行和列后得到的矩陣,其特征多項(xiàng)式記為Φ(Dn),規(guī)定Φ(D0)=1,Φ(D-n)=0.則

(1)xΦ(Dn-1)=Φ(Pn)；

(2)Φ(Dn+1)=(x-2)Φ(Dn)-Φ(Dn-1)；

(3)Φ(Dm+1)Φ(Dn)-Φ(Dm)Φ(Dn+1)=Φ(Dm)Φ(Dn-1)-Φ(Dm-1)Φ(Dn)；

(4)Φ(Cn)=Φ(Dn)-Φ(Dn-2)+2(-1)n+1．

引理2給定n階矩陣Dn(n≥1),則Φ2(Dn)=Φ(Dn+1)Φ(Dn-1)+1．

證明由引理1(2)可知,

兩邊取行列式可得

Φ2(Dn)-Φ(Dn+1)Φ(Dn-1)=Φ2(Dn-1)-Φ(Dn)Φ(Dn-2)=…=Φ2(D1)-Φ(D2)Φ(D0)=1

引理3給定n階矩陣Dn(n≥1),則當(dāng)x≥4時(shí),Φ(Dn)>Φ(Dn-1)．

證明利用數(shù)學(xué)歸納法:

當(dāng)k=1時(shí),Φ(D1)=x-2,Φ(D0)=1,故當(dāng)x≥4時(shí),Φ(D1)>Φ(D0)．

假設(shè)當(dāng)k≤n時(shí),Φ(Dk)>Φ(Dk-1)．

當(dāng)k=n+1時(shí),由引理1(2)及假設(shè)知,

Φ(Dn+1)-Φ(Dn)=(x-3)Φ(Dn)-Φ(Dn-1)> (x-4)Φ(Dn-1)≥0

故結(jié)論成立．

下面給出單圈圖的一些變換性質(zhì)．

證明不妨用k表示任意的大于3的正整數(shù),由引理1(4)及文獻(xiàn)[10]中引理1知,

(1)

當(dāng)x≥r2時(shí),P(x,k)>0；由引理3知P(4,k)<0；進(jìn)一步

其中sgn為實(shí)數(shù)集R上的符號(hào)函數(shù),即

情形1若存在指標(biāo)m滿足μm(Dk-1)=r1,那么

由Φ(Dk)的根的特點(diǎn)可知1

情形2若存在指標(biāo)m滿足μm+1(Dk)≤r1<μm(Dk-1),那么sgn(P(μm+1(Dk),k))=(-1)m, sgn(P(μm(Dk-1),k))=(-1)m-1,因此P(x,k)在區(qū)間(μm+1(Dk),μm(Dk-1))內(nèi)至少有一個(gè)實(shí)根,取代了情形1中的實(shí)根r1,其他區(qū)間內(nèi)根的情況類似于情形1．

情形3若存在指標(biāo)m滿足μm+1(Dk-1)

綜上,P(x,k)至少有k+1個(gè)實(shí)根,而P(x,k) 是k+2次多項(xiàng)式,故其余的根必定是實(shí)數(shù)．下面說(shuō)明P(x,k)在(4,r2)內(nèi)僅有一個(gè)根c(k),且為P(x,k)的最大根．不然,若(4,c(k)]內(nèi)還有一個(gè)根d,由P(x,k)的連續(xù)性及根的分布特點(diǎn)可知,當(dāng)x∈(4,d)時(shí),P(x,k)<0,與P(x,k)>0矛盾．由此可見(jiàn),P(x,k)的第二大根是小于4的．

下面考慮P(x,k)的最大根c(k)隨k嚴(yán)格遞減且有下界．

由Maple計(jì)算可知,c(4)=4.385 7,c(5)=4.384 7,故c(4)>c(5),假設(shè)c(k-1)>c(k)成立,由于P(x,k+1)-(x-2)P(x,k)=-P(x,k-1),等式兩邊取x=c(k),由假設(shè)可知,c(k)>c(k+1)．

此外,P2(x,k)-P(x,k-1)P(x,k+1)=(x-4)(x3-6x2+8x-4),由Maple計(jì)算得到x3-6x2+8x-4=0的最大根為e=4.383 7,若存在l,使得c(l)≤e0,與(x-4)(x3-6x2+8x-4)|x=e=0矛盾．因而,c(k)單調(diào)遞減且有下界e,但永遠(yuǎn)達(dá)不到下界．

證明通過(guò)直接計(jì)算可得

(2)

由于Dk-2-2a的最大特征值小于4,由文獻(xiàn)[10]的引理6知,當(dāng)

時(shí),式(2)大于零,從而結(jié)論成立．

2 主要結(jié)論

(3)

其中a+b=k-2．特別地,當(dāng)a=1,有以下定理．

證明不妨設(shè)k為任意的大于4的正整數(shù),由式(3)可知

(4)

當(dāng)x≥5時(shí),Q(x,k)>0；由引理1(2)知Q(4,k)<0,考慮s1在區(qū)間(μk(Dk),μ1(Dk))內(nèi)的位置．

若存在指標(biāo)m滿足μm(Dk)=s1,那么由Φ(Dk)的根的特點(diǎn)可知1

而Q(x,k)的最大根d(k)隨k嚴(yán)格遞增且有上界．

由Maple計(jì)算可知,d(4)=4.379 9,d(5)=4.382 8,故d(4)

此外,Q2(x,k)-Q(x,k-1)Q(x,k+1)=-x(x3-6x2+8x-4),由Maple計(jì)算得到x3-6x2+8x-4=0最大根為e=4.383 7,若存在m,使得d(m)≥e>d(m-1),那么Q2(x,m)-Q(x,m-1)Q(x,m+1)|x=e>0,與-x(x3-6x2+8x-4)|x=e=0矛盾．因而,d(k)嚴(yán)格遞增且有上界e,但永遠(yuǎn)達(dá)不到上界．

證明由引理1(2)和2,式(3)變?yōu)?/p>

(5)

令W(x,t)=Φ(Dt)-2Φ(Dt-1)=(x-4)Φ(Dt-1)-Φ(Dt-2),t≥2．

由引理3知,對(duì)任意的x≥5,W(x,t)>0；W(4,t)<0．進(jìn)一步,

由連續(xù)函數(shù)的零點(diǎn)定理知,W(x,t)在每個(gè)區(qū)間(μt(Dt),μt-1(Dt-1)),…,(μ2(Dt),μ1(Dt-1)),(4,5)內(nèi)至少有一個(gè)實(shí)根,而W(x,t)的次數(shù)恰好為t,因而W(x,t)的第二大根小于4,記它的最大根為w(t)．

W(x,t)的最大根w(t)隨t嚴(yán)格遞增且有上界．

由Maple計(jì)算可知,w(1)=4,w(2)=4.415 0,故w(1)

此外,W2(x,t)-W(x,t-1)W(x,t+1)=9-2x,其最大根為4.5,若存在n,使得w(n)≥4.5>w(n-1),那么W2(x,n)-W(x,n-1)W(x,n+1)|x=4.5>0,與9-2x|x=4.5=0矛盾．因而,w(t)嚴(yán)格遞增且有上界4.5,但永遠(yuǎn)達(dá)不到上界．

由定理1、2和引理5可知下面定理．

3 結(jié) 語(yǔ)

[1]Anderson W N, Morley T D. Eigenvalues of the Laplacian of a graph [J]. Linear and Multilinear Algebra, 1985,18(2):141-145.

[2]Cvetkovic D, Doob M, Sachs H. Spectra of Graphs-Theory and Application [M]. New York:Academic Press, 1980.

[3]Kinkar C D. The Laplacian spectrum of a graph [J]. Computers and Mathematics with Applications, 2004,48(5-6):715-724.

[4]LI Jiong-sheng, ZHANG Xiao-dong. A new upper bound for eigenvalues of Laplacian matrix of a graph [J]. Linear Algebra and Its Applications, 1997,265(1-3):93-100.

[5]LI Jiong-sheng, ZHANG Xiao-dong. On the Laplacian eigenvalues of a graph [J]. Linear Algebra and Its Applications, 1998,285(1-3):305-307.

[6]Merris R. Laplacian matrices of graphs:A survey [J]. Linear Algebra and Its Applications, 1994,197-198:143-176.

[7]Merris R. A note on Laplacian graph eigenvalues [J]. Linear Algebra and Its Applications, 1998,285(1-3):33-35.

[8]Cvetkovic D, Rowlinson P. Spectra of unicyclic graphs [J]. Graphs and Combinatorics, 1987,3(1):7-23.

[9]郭曙光. 單圈圖Laplace矩陣的最大特征值[J]. 高等應(yīng)用數(shù)學(xué)學(xué)報(bào):A輯, 2001,16(2):131-135.

GUO Shu-guang. The largest eigenvalues of Laplacian matrix of unicyclic graphs [J]. Applied Mathematics Journal of Chinese Universities:Series A, 2001,16(2):131-135. (in Chinese)

[10]張海霞,于洪全. 按Laplace譜半徑對(duì)圈長(zhǎng)和階數(shù)固定的單圈圖的排序[J]. 大連理工大學(xué)學(xué)報(bào), 2013,53(1):145-150.

ZHANG Hai-xia, YU Hong-quan. Unicyclic graphs ordering with fixed number vertices and cycle length by their Laplace spectral radii [J]. Journal of Dalian University of Technology, 2013,53(1):145-150. (in Chinese)

[11]GUO Ji-ming. A conjecture on the algebraic connectivity of connected graphs with fixed girth [J]. Discrete Mathematics, 2008,308(23):5702-5711.

[12]GUO Ji-ming. The Laplacian spectral radius of a graph under modifications [J]. Computers and Mathematics with Applications, 2007,54(5):709-720.

Someeven-unicyclicgraphsorderingbytheirLaplacianspectralradii

ZHANG Hai-xia*1,2

( 1.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China;2.Department of Mathematics, Taiyuan University of Science and Technology,Taiyuan 030024, China )

unicyclic graphs; maximum Laplacian eigenvalues; ordering

1000-8608(2014)01-0152-05

2012-11-23；

: 2013-09-21．

山西省自然科學(xué)基金資助項(xiàng)目(2012011019-2)；太原科技大學(xué)校青年基金資助項(xiàng)目(20113022)．

張海霞*(1979-),女,博士生,講師,E-mail:zhx049@163.com．

O157.5

：A

10.7511/dllgxb201401023