张欢欢, 施劲松

(华东理工大学数学系,上海 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点对应的分量。由