图依谱半径的排序

张欢欢, 施劲松

(华东理工大学数学系,上海 200237)

图依谱半径的排序

张欢欢, 施劲松

(华东理工大学数学系,上海 200237)

n阶(n≥6)简单连通无向图G的谱半径记为ρ(G)。依G的谱半径从大到小进行了排序,得到如下结果:ρ(Kn)>ρ(Kn-K2)>ρ(Kn-P3)>ρ(Kn-2K2)>ρ(Kn-K1,3)>ρ(Kn-C3)>ρ(Kn-P4)>ρ(Kn-P3∪K2)。

邻接矩阵; 谱半径; 极图

有了这些界的基础,就可以对特殊图类谱半径的大小进行排序。郭曙光等[6]刻画了前九大拉普拉斯谱半径对应的单圈图。随后,刘颖等[7]将上述结论进一步推广到了前十三大的单圈图。但至今为止,鲜有对一般图谱半径排序的相关研究。本文刻画了在所有的简单连通无向图中,前八大谱半径对应的图。本文中的图,若非特别声明,都是指简单连通无向图。其他符号的定义,参考文献[8]。

1 预备知识

引理2[4]设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设A和B为n阶Hermite矩阵,其中ρ(A)、ρ(B)分别为A、B的谱半径。若A≥B,则ρ(A)≥ρ(B),等号成立当且仅当A=B。

此外,关于谱半径ρ(G)和最大度Δ、最小度δ之间的关系,成立:

引理5[9]令f(x)和g(x)为两个首1的有实数根的多项式,∂(f)、λ1(f)分别表示多项式f(x)的最高次数和最大根。若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 主要结论

下面比较G(n,M-2)中所有图的谱半径大小:

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

证明 令G=Kn-P3为Kn中删去两条边v1v2,v2v3得到的图,H=Kn-2K2为Kn中删去两条边v1v2,v3v4得到的图。设图H的谱半径ρ(H)对应的Perron向量为x=(x1,x2,……,xn)T,其中xi为图中vi点对应的分量。由

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

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

下面证明不等号严格成立,若等号成立则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得到的图。设y1、y2、y3、y4分别为ρ(G1),ρ(G2),ρ(G3),ρ(G4)对应的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)分别为以下多项式的零点:

条码技术在食品行业中推广使用的意义。当商品的各种“说明书”下架之后，人们对食品的物理形态能够一目了然，但是对食品的其他特性却无法通过物理形态准确知晓，特别是市场上出现了很多食品不达标的负面报道之后，广大消费者对食品的安全性更加关心。如果食品企业用上条码技术，消费者利用手机等设备扫描食品包装上的条码，就能熟知食品的产地、生产者、加工情况、农药残留、食品等级、检测结果等内容，有利于消费者选择安全、符合自身营养需求的食品。而且，食品行业使用条码技术可以节省消费者的时间，他们购买已贴好条码的食品，无需去排队打秤，甚至无需在长长的人工收款队伍里排队，可以直接在自动收款机付款[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个多项式的最大零点即为对应图的谱半径。

因为f1(-n2)<0,f1(0)=2(n-4)>0,f1(1)=2-n<0 (n≥7),f1(n2)>0,所以f1=0有3个根,且分别属于区间(-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的最大根。

现在比较ρ(G1)、ρ(G2)的大小关系。ρ(G1)、ρ(G2)对应的两个多项式满足以下关系:

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

下面比较ρ(G3),ρ(G4)的大小关系。ρ(G3)、ρ(G4)对应的两个多项式满足以下关系:

(λ+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不连通,则考虑其连通分支数分别为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有实数根,且分别属于区间(-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)对应的Perron向量,ui为点vi对应的分量)得谱半径ρ(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有实数根,且分别属于区间(-n,0)、(0,1)和(1,n)。由引理4可知ρ(Kn-H6)>δ(Kn-H6)=n-5>1,所以ρ(Kn-H6)必为方程Q(λ)=0的最大根。

接下来比较P(λ)=0,Q(λ)=0的最大根与f4(λ)=0的最大根之间的大小关系。由P(λ)=f4(λ)+λ2+(n-5)λ,因为f4(λ)=0的最大根ρ(G4)>0,所以当λ=ρ(G4)时,r(λ)=λ2+(n-5)λ>0。由引理5的(2)可得λ1(f4)>λ1(P(λ)),即ρ(Kn-P3∪K2)>ρ(Kn-H1)成立。

同理,由f4(λ)=(λ+2)Q(λ)+(10-2n)λ+22-4n,再结合引理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中的图的谱半径的大小关系,可以得到G(n,m)中谱半径最大的前八大图,即成立:

定理1在所有的简单连通无向图G(n,m)中,依谱半径从大到小的排序结果为:ρ(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)。又当k>4时G(n,M-k)中任意一个图都可以在G(n,M-4)中找到相应的真子图,所以由引理3可知G(n,M-k)(k≥4)中任意图的谱半径都小于ρ(Kn-P3∪K2)。

结合推论1即得最终排序结果:

ρ(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].高校应用数学学报,2001,16(2):131-135.

[7] 刘颖,刘月.单圈图的Laplace谱半径的排序[J].同济大学学报(自然科学版),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-),女,安徽人,硕士生,研究方向为图论及其应用。E-mail:396366937@qq.com

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

O157.5

A