張歡歡, 施勁松

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

圖依譜半徑的排序

張歡歡, 施勁松

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

n階(n≥6)簡單連通無向圖G的譜半徑記為ρ(G)。依G的譜半徑從大到小進行了排序,得到如下結(jié)果:ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2)。

鄰接矩陣; 譜半徑; 極圖

有了這些界的基礎(chǔ),就可以對特殊圖類譜半徑的大小進行排序。郭曙光等[6]刻畫了前九大拉普拉斯譜半徑對應(yīng)的單圈圖。隨后,劉穎等[7]將上述結(jié)論進一步推廣到了前十三大的單圈圖。但至今為止,鮮有對一般圖譜半徑排序的相關(guān)研究。本文刻畫了在所有的簡單連通無向圖中,前八大譜半徑對應(yīng)的圖。本文中的圖,若非特別聲明,都是指簡單連通無向圖。其他符號的定義,參考文獻[8]。

1 預(yù)備知識

引理2[4]設(shè)A為n階Hermite矩陣,其中λ1(A)≥λ2(A)≥…≥λn(A)為A的特征值,若B為A的m階主子矩陣,且μ1(A)≥μ2(A)≥…≥μm(A)為B的特征值,則成立λn-m+i(A)≤ui(B)≤λi(A),(i=1,2,3,…,m)。

對兩個n階矩陣A和B,若A中每個元素都大于等于B中相同位置的元素,則記作A≥B;在A≥B時,若A中還至少有一個元素大于B中相同位置的元素,則記為A>B。

由引理2可得到:

引理3設(shè)A和B為n階Hermite矩陣,其中ρ(A)、ρ(B)分別為A、B的譜半徑。若A≥B,則ρ(A)≥ρ(B),等號成立當(dāng)且僅當(dāng)A=B。

此外,關(guān)于譜半徑ρ(G)和最大度Δ、最小度δ之間的關(guān)系,成立:

引理5[9]令f(x)和g(x)為兩個首1的有實數(shù)根的多項式,?(f)、λ1(f)分別表示多項式f(x)的最高次數(shù)和最大根。若f(x)=g(x)q(x)+r(x)(?(f)≥?(g)),其中q(x)也為首1的多項式,且滿足?(r)≤?(g)和λ1(g)>λ1(q),則成立:

(1)r(x)=0,則λ1(f)=λ1(g);

(2) 若對于任意的x>λ1(g)有r(x)>0,則λ1(f)<λ1(g);

(3) 若r(λ1(g))<0,則λ1(f)>λ1(g)。

2 主要結(jié)論

下面比較G(n,M-2)中所有圖的譜半徑大小:

引理7ρ(Kn-P3)>ρ(Kn-2K2)。

證明 令G=Kn-P3為Kn中刪去兩條邊v1v2,v2v3得到的圖,H=Kn-2K2為Kn中刪去兩條邊v1v2,v3v4得到的圖。設(shè)圖H的譜半徑ρ(H)對應(yīng)的Perron向量為x=(x1,x2,……,xn)T,其中xi為圖中vi點對應(yīng)的分量。由

ρ(G)-ρ(H)≥xTA(G)x-xTA(H)x=

2x2x3-2x3x4=2x3(x2-x4)

下面證明不等號嚴(yán)格成立,若等號成立則x=(x1,x2,……xn)T也為A(G)的特征向量,由A(G)x=ρ(G)x可得ρ(G)x2=(n-3)x4;又由A(H)x=ρ(H)x可得ρ(H)x2=x3+x4+(n-4)x5=x3+(n-3)x4;由ρ(G)x=ρ(H)x,可以得到(n-3)x4=x3+(n+3)x4,進而x3=0,矛盾。所以ρ(G)>ρ(H)。引理得證。

接下來,比較G(n,M-3)中圖的譜半徑大小:

引理8令ρ(G1),ρ(G2),ρ(G3),ρ(G4)分別為G1=Kn-K1,3、G2=Kn-C3、G3=Kn-P4、G4=Kn-P3∪K2的譜半徑,其中n≥6,則ρ(G1)>ρ(G2)>ρ(G3)>ρ(G4)。

證明 令G1=Kn-K1,3為Kn刪去邊v1v2,v1v3,v1v4得到的圖,G2=Kn-C3為Kn刪去邊v1v2,v2v3,v3v1得到的圖,G3=Kn-P4為Kn刪去邊v1v2,v2v3,v3v4得到的圖,G4=Kn-P3∪K2為Kn刪去邊v1v2,v2v3,v4v5得到的圖。設(shè)y1、y2、y3、y4分別為ρ(G1),ρ(G2),ρ(G3),ρ(G4)對應(yīng)的Perron向量,yij為yi(1≤i≤4)的第j(1≤j≤n)個分量。

對圖G1=Kn-K1,3由A(G1)y1=ρ(G1)y1可得:

化簡得譜半徑ρ(G1)為下列多項式的零點:

f1=f1(λ)=λ3-(n-3)λ2-(2n-6)λ+2(n-4)。

同理可得ρ(G2),ρ(G3),ρ(G4)分別為以下多項式的零點:

條碼技術(shù)在食品行業(yè)中推廣使用的意義。當(dāng)商品的各種“說明書”下架之后，人們對食品的物理形態(tài)能夠一目了然，但是對食品的其他特性卻無法通過物理形態(tài)準(zhǔn)確知曉，特別是市場上出現(xiàn)了很多食品不達標(biāo)的負面報道之后，廣大消費者對食品的安全性更加關(guān)心。如果食品企業(yè)用上條碼技術(shù)，消費者利用手機等設(shè)備掃描食品包裝上的條碼，就能熟知食品的產(chǎn)地、生產(chǎn)者、加工情況、農(nóng)藥殘留、食品等級、檢測結(jié)果等內(nèi)容，有利于消費者選擇安全、符合自身營養(yǎng)需求的食品。而且，食品行業(yè)使用條碼技術(shù)可以節(jié)省消費者的時間，他們購買已貼好條碼的食品，無需去排隊打秤，甚至無需在長長的人工收款隊伍里排隊，可以直接在自動收款機付款[2]。

f2=f2(λ)=λ2+(4-n)λ-3(n-3),

f3=f3(λ)=λ3-(n-4)λ2-(3n-10)λ-(n-3),

f4=f4(λ)=λ4-(5-n)λ2-(2n-6)λ+2(n-4)。

下面證明以上4個多項式的最大零點即為對應(yīng)圖的譜半徑。

因為f1(-n2)<0,f1(0)=2(n-4)>0,f1(1)=2-n<0 (n≥7),f1(n2)>0,所以f1=0有3個根,且分別屬于區(qū)間(-n2,0)、(0,1)、(1,n2)。由引理4可知ρ(G1)>δ(G1)=n-4,所以ρ(G1)?(-n2,0)∪(0,1),進而ρ(G1)為f1=0的最大根。同理可證ρ(G2),ρ(G3),ρ(G4)分別為f2=0,f3=0,f4=0的最大根。

現(xiàn)在比較ρ(G1)、ρ(G2)的大小關(guān)系。ρ(G1)、ρ(G2)對應(yīng)的兩個多項式滿足以下關(guān)系:

f1=(λ-1)f2+λ-n+1,因為ρ(G2)<Δ(G2)=n-1,由引理5的(3),可得ρ(G1)>ρ(G2)。

下面比較ρ(G3),ρ(G4)的大小關(guān)系。ρ(G3)、ρ(G4)對應(yīng)的兩個多項式滿足以下關(guān)系:

(λ+1)f3-f4=λ2+(2-n)λ+11-3n=

λ(λ+2-n)+11-3n

f4=(λ+1)f3-λ(λ+2-n)+3n-11

由引理4可知G3、G4的譜半徑滿足n-3<ρ(G3)、ρ(G4)ρ(G4)。

類似可知f3=λf2+λ-(n-3),由引理4知ρ(G2)>n-3>0,由引理5的(2)可得ρ(G2)>ρ(G3)。

綜上可得ρ(G1)>ρ(G2)>ρ(G3)>ρ(G4),引理得證。

綜合引理6,引理7,引理8,可得以下圖類的譜半徑滿足:

推論1ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2)>ρ(Kn-3K2)。

ρ(Kn-2K2)=

將ρ(Kn-2K2)代入引理8中的f1,計算可得:

所以ρ(Kn-2K2)>ρ(Kn-K1,3)。

再將ρ(Kn-3K2)代入引理 8中的f4,計算可得:

所以ρ(Kn-3K2)<ρ(Kn-P3∪K2)。

綜上可得以下不等式成立:

ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>

ρ(Kn-2K2)>ρ(Kn-K1,3)>

ρ(Kn-C3)>ρ(Kn-P4)>

ρ(Kn-P3∪K2)>ρ(Kn-3K2)。

推論得證。

下面考慮Kn刪去4條邊的情況,記G(n,M-4)={Kn-Hi,i=1,2,…,11},接下來,考慮Hi的情形,圖1示出了G(n,M-4)中的11個圖。若Hi含圈,則其必為單圈圖且圈長最大為4,即只有圖1中的H1,H2,H3。除單圈圖外,Hi若為連通圖,則按照其最長路的長度枚舉可得只有下圖中的H4,H5,H6這3種情況。若Hi不連通,則考慮其連通分支數(shù)分別為2、3、4時的情況,最終可得:G(n,M-4)={Kn-Hi,i=1,2,…,11}。

最后,說明G(n,M-4)中11個圖的譜半徑均小于ρ(Kn-P3∪K2)。

圖1 G(n,M-4)中的11個圖Fig.1 11 Graphs in G(n,M-4)

引理9n≥8時,對于任意的Kn-Hi∈G(n,M-4)(1≤i≤11)有ρ(Kn-P3∪K2)>ρ(H)。

化簡得ρ(Kn-H2)為以下多項式的零點:

P(λ)=λ4+(5-n)λ3+(14-4n)λ2+

(6-2n)λ+2n-8。

由P(-n2)>0,P(-2)=12-2n<0,P(0)=2(n-4)>0,P(1)=18-5n<0,P(n2)=n3+12n2+8n-8>0可知,P(λ)=0有實數(shù)根,且分別屬于區(qū)間(-n2,-2)、(-2,0)、(0,1)和(1,n2)。由引理4可知,ρ(Kn-H2)>δ(Kn-H2)=n-4>1,所以ρ(Kn-H2)必為方程P(λ)=0的最大根。

同理,由A(Kn-H6)u=ρ(Kn-H6)u(其中u為譜半徑ρ(Kn-H6)對應(yīng)的Perron向量,ui為點vi對應(yīng)的分量)得譜半徑ρ(Kn-H6)滿足方程組:

化簡得ρ(Kn-H6)為以下多項式的零點:

Q(λ)=λ3+(3-n)λ2+(7-2n)λ+3(n-5)。

由Q(-n)<0,Q(0)=3(n-5)>0,Q(1)=-4<0,Q(n)=n2+10n-15>0可知Q(λ)=0有實數(shù)根,且分別屬于區(qū)間(-n,0)、(0,1)和(1,n)。由引理4可知ρ(Kn-H6)>δ(Kn-H6)=n-5>1,所以ρ(Kn-H6)必為方程Q(λ)=0的最大根。

接下來比較P(λ)=0,Q(λ)=0的最大根與f4(λ)=0的最大根之間的大小關(guān)系。由P(λ)=f4(λ)+λ2+(n-5)λ,因為f4(λ)=0的最大根ρ(G4)>0,所以當(dāng)λ=ρ(G4)時,r(λ)=λ2+(n-5)λ>0。由引理5的(2)可得λ1(f4)>λ1(P(λ)),即ρ(Kn-P3∪K2)>ρ(Kn-H1)成立。

同理,由f4(λ)=(λ+2)Q(λ)+(10-2n)λ+22-4n,再結(jié)合引理4可知λ1(Q)>δ(Kn-H6)=n-5,所以對r(λ)=(10-2n)λ+22-4n有r(λ1(Q))<0,由引理5的(3)可得λ1(f4)>λ1(Q(λ))即ρ(Kn-P3∪K2)>ρ(Kn-H6)。綜上,引理得證。

綜合推論1和引理9中的圖的譜半徑的大小關(guān)系,可以得到G(n,m)中譜半徑最大的前八大圖,即成立:

定理1在所有的簡單連通無向圖G(n,m)中,依譜半徑從大到小的排序結(jié)果為:ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2)。

證明 由引理9可知集合G(n,M-4)中任意圖的譜半徑均小于ρ(Kn-P3∪K2)。又當(dāng)k>4時G(n,M-k)中任意一個圖都可以在G(n,M-4)中找到相應(yīng)的真子圖,所以由引理3可知G(n,M-k)(k≥4)中任意圖的譜半徑都小于ρ(Kn-P3∪K2)。

結(jié)合推論1即得最終排序結(jié)果:

ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2)。定理得證。

[1] CAO Dasong.Bounds on eigenvalues and chromatic number[J].Linear Algebra Applications,1998,270(1-3):1-13.

[2] LIU Bolian.On sharp bounds of the spectral radius of graphs[J].Univerzitetu u Beogradu Publikacija Elektrotehnickog Fakulteta-Serija Matematika,1998,9:55-59.

[3] HONG Yuan,SHU Jinlong,FANG Kunfu.A sharp upper bound of the spectral radius of graphs[J].Journal of Combinatorial Theory,Series B81,2001,81:177-183.

[4] KINKAR C D,PAWAN K.Some new bounds on the spectral radius of graphs[J].Discrete Mathematics,2004,281(1-3):149-161.

[5] SHU Jinlong,WU Yarong.Sharp upper bounds on the spectral radius of graphs[J].Linear Algebra Applications,2004,377(1):241-248.

[6] 郭曙光.單圈圖的Laplace譜的最大特征值[J].高校應(yīng)用數(shù)學(xué)學(xué)報,2001,16(2):131-135.

[7] 劉穎,劉月.單圈圖的Laplace譜半徑的排序[J].同濟大學(xué)學(xué)報(自然科學(xué)版),2008,36(6):841-844.

[9] CHANG An.On the largest eigenvalue of a tree with perfect matchings[J].Discrete Mathematics,2003,269:45-63.

OrderingGraphsbyTheirSpectralRadii

ZHANGHuan-huan,SHIJin-song

(DepartmentofMathematics,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

LetGbe a simple connected graph of ordern(n≥6) with spectral radiusρ(G).This paper gives the first eight largest spectral radii of graphsρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2).

adjacency matrices; spectral radii; extremal graphs

1006-3080(2017)06-0885-05

10.14135/j.cnki.1006-3080.2017.06.020

2016-04-28

張歡歡,(1991-),女,安徽人,碩士生,研究方向為圖論及其應(yīng)用。E-mail:396366937@qq.com

施勁松,E-mail:jsshi@ecust.edu.cn

O157.5

A