張 海 霞

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

?

按Laplace譜半徑對一些偶單圈圖的排序

張 海 霞*1,2

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

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

0 引 言

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

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

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

1 用到的引理

引理1[11]記Dn是n階矩陣,它是從路Pn+2對應(yīng)的L(Pn+2)(n≥1)中刪掉兩個懸掛點所對應(yī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時,Φ(Dn)>Φ(Dn-1)．

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

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

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

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

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

故結(jié)論成立．

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

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

(1)

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

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

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

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

情形2若存在指標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)至少有一個實根,取代了情形1中的實根r1,其他區(qū)間內(nèi)根的情況類似于情形1．

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

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

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

由Maple計算可知,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計算得到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,但永遠達不到下界．

證明通過直接計算可得

(2)

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

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

2 主要結(jié)論

(3)

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

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

(4)

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

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

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

由Maple計算可知,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計算得到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)嚴格遞增且有上界e,但永遠達不到上界．

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

(5)

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

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

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

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

由Maple計算可知,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)嚴格遞增且有上界4.5,但永遠達不到上界．

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

3 結(jié) 語

[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é)報: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譜半徑對圈長和階數(shù)固定的單圈圖的排序[J]. 大連理工大學(xué)學(xué)報, 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é)基金資助項目(2012011019-2)；太原科技大學(xué)校青年基金資助項目(20113022)．

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

O157.5

：A

10.7511/dllgxb201401023