图谱半径的可达上界与可达下界

房启明, 左连翠

(天津师范大学 数学科学学院, 天津 300387)

1 图谱半径可达上界与可达下界的讨论

本文所讨论的图均为连通的简单图。

给定一个n点简单图G=(V,E)，V={v1,v2,…,vn}，d1≥d2≥…≥dn为图G的度序列，|E|表示图G中边的条数。设图G的邻接矩阵为A(G)=(aij)n×n，其中aij为vi与vj之间边的条数，用i～j表示vi与vj相邻，此时aij=1；如果vi与vj不相邻，那么aij=0。A(G)的特征值称为图G的特征值。图G的所有特征值组成的集合即为图G的谱。图G的最大特征值即为图G的谱半径。将A(G)的特征值按照非增序列排序，得到λ1≥λ2≥…≥λn，其中λ1为图G的谱半径，而{λ1,λ2,…,λn}称为图G的谱。

图G的度对角矩阵为D(G)=diag(d1,d2,…,dn)，其中d1≥d2≥…≥dn。图G的拉普拉斯矩阵L(G)定义为L(G)=D(G)-A(G)，而L(G)的特征值称为图G的拉普拉斯特征值，图G的拉普拉斯谱由所有的拉普拉斯特征值构成。

图G的拟拉普拉斯矩阵Q(G)定义为Q(G)=D(G)+A(G)，而Q(G)的特征值称为图G的拟拉普拉斯特征值，图G的拟拉普拉斯谱由所有的拟拉普拉斯特征值构成。

文中未说明的术语和符号参见文献[1-3]。

图G的邻接矩阵的最大特征值λ1即为图G的谱半径。文献[4]给出了图的拟拉普拉斯谱半径的一个可达上界

图的谱半径、图的拉普拉斯谱半径与图的拟拉普拉斯谱半径之间也存在着联系，参考文献[5-7]主要讨论了它们之间的大小关系，其中文献[7]得到以下结论:

2λ1≤q1，

(1)

尝试给出λ1的一个可达上界，使得当q1达到其上界时，λ1同样达到其上界。在此基础上，给出λ1的一个可达下界。最后，将得到的上界、下界和引理3与引理4中的上界、下界进行比较，并证明在一定条件下得到的上界和下界更好。

2 主要结论及证明

定义1[4]设连通的简单图H=(V,E)有n个顶点，且满足V(H)={v1}∪V1∪V2。设d1=Δ1，V1={vk|k～1,dk=δ},V2={vk|vk与v1不相邻，dk=Δ2}，其中Δ1，Δ2，δ满足Δ1=Δ2(1+Δ2-δ)。Ψ为所有满足上述条件的图H所构成的集合。

定义2[4]如果一个简单图有一个n-1度点，其余的点的度数均为Δ2<(n-1)，则称这样的图为(n-1,Δ2)半正则图。Φ为所有满足上述条件的图所构成的集合。

引理1[8]设M是非负不可约矩阵，ρ(M)是其谱半径，则有结论:

(1)M有一正实特征值恰好等于它的谱半径ρ(M)；

(2)存在一个正向量X使得MX=ρ(M)X；

(3)当M的任意元素(一个或多个)增加时，其谱半径不减少。

引理2[4]设连通图G的度序列为d1≥d2≥…≥dn，则其拟拉普拉斯矩阵的最大特征值满足

当且仅当G是正则图或G∈Ψ或G∈Φ时，等号成立。

引理3[9]设图G为具有n个顶点的简单连通图，不妨设其顶点度序列满足d1≥d2≥…≥dn，则

对于任意的1≤l≤n都成立。

进一步，当l=1时，等式成立当且仅当G是正则图；当2≤l≤n时，等式成立当且仅当G为满足d1=d2=…=dl-1=n-1，dl=dl+1=…=dn=η的二度图。

引理4[10]设图G为具有n个顶点的简单连通图，不妨设其顶点度序列满足d1≥d2≥…≥dn，则

当且仅当G是正则图时，等式成立。

定理1 设连通图G的度序列为d1≥d2≥…≥dn，则

(2)

当且仅当G是正则图或G∈Ψ或G∈Φ时，等号成立。

由于A(G)X=λ1X，那么对于第i行，有

(3)

所以，对于第j行，有

从而

(λ1-dj+1)xj≤1,

(4)

(3)与(4)式两端分别相乘，再消去xj,得

λ12-(dj-1)λ1-di≤0,

那么，根据λ1是正的特点可得

下证

若想让(2)式中等号成立，则(3)、(4)两式中等号必须成立，因此

(5)

(6)

且当(4)式中等号成立时，一定有i～j。

设V0={vk|xk=xj}。假设V0≠V{vi}，则存在vp与vq，使得p～q，vp∈V0,vqV0且vq≠vi。因为xj为第二大的分量，且xp=xj，所以xq

若xj=1，此时λ1=di(i=1,2,…,n)，因此图G中所有点的度数均相同，为正则图。此时(2)式中等号成立。即

若xj≠1，此时分两种情况讨论。

情况1di=n-1。

情况2di

设V1={vk|k～i}，V2={vk|vk与vi不相邻}。则由(3)式可得

λ1=dixj，

(7)

即

若vj∈V1，由(4)式可得

(8)

即

若vk∈V2，由(6)式，易得

λ1xk=dkxk，

(9)

即

λ1=dk,

亦即

设Δ1=di,δ=dj,Δ2=dk。联立(7)、(8)、(9)三式,可得

Δ1=Δ2(1+Δ2-δ),

且有Δ1>Δ2>δ，所以G∈Ψ。

由(7)、(8)两式，易得di≥dj。(7)、(8)两式相乘,并消去xj，得

综上所述，得出

仅当G是正则图或G∈Ψ或G∈Φ时，等号成立。

反之，推出当G是正则图或G∈Ψ或G∈Φ时，(2)式等号成立。此定理得证。

推论1λ1≤n-1。

证明由定理1容易得出，

推论2 设图G的度序列为d1≥d2≥…≥dn，则λ1≥dn。

证明设正则图G′的度序列为{d1,d2,…，dn}，则由定理1，正则图G′的谱半径为dn。由引理1，当G′中的任意顶点的度(一个或多个)增加时，其谱半径不减少,因此有λ1≥dn。

对比定理1与引理2，当G是正则图，G∈Ψ或G∈Φ时，G的谱半径λ1与G的拟拉普拉斯矩阵的谱半径q1同时取到最大值。并且当G为正则图时，(1)式取等号，此时有2λ1=q1。

讨论图G的谱半径的一个可达下界。

定理2 设连通图G的度序列为d1≥d2≥…≥dn，则

(10)

当且仅当G是正则图或G∈Φ时，等号成立。

由于A(G)X=λ1X，对于第p行，有

(11)

对于第q行，有

即

(λ1-dq+1)xq≥1。

(12)

(11)式与(12)式两端分别相乘，再消去xq，得

λ12-(dq-1)λ1-dp≥0,

因此

(13)

如果(13)式中等号成立，则(11)、(12)两式中等号必然成立。当(12)式中等号成立时，必然有p～q，因此

结合定理1，得到

综上所述，(10)式得证。

当G∈Ψ时，很容易举出反例，使得

图1 图G

此时(10)式中的等式无法成立。例如Δ1=6，δ=2，Δ2=3，则图G如图1所示。此时

显然二者不相等。

当图G为k-正则图或G∈Φ时，易得

此时(10)式中的等式成立,即

将定理1与引理3的结论相比较得到，

显然，在一定条件下，定理1的结论优于引理3。并且，仅在两种极其特殊的情形下，引理3中的等式才成立；而定理1中等式成立的情况更多，涵盖范围更广(例如G∈Ψ时，定理1中等式成立，而引理3中等式不成立)。因此，上述得到的上界更好。

将定理2与引理4的结论相比较。

情况1 设树图G的度序列为d1≥d2≥…≥dr≥dr+1≥…≥dn。设dr+1=dr+2=…=dn=1，且dr>1。如果图G中的第二小度点的度数大于等于4，即dr≥4，则由定理2得，

由引理4得，

在这种情况下，定理2优于引理4。

由引理4得

情况3 当G∈Φ时，定理2等式成立，引理4中等式不成立，在这种情况下，定理2优于引理4。

由此可见,定理2在一些情况下优于引理4，所以在使用时要视情况而定。

[参考文献]

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: Macmillan Press,1976:1-24.

[2] 程云鹏.矩阵论[M].4版.西安:西北工业大学出版社,2013:234-288.

[3] MOHAR B. On the sum ofklargest eigenvalues of graphs and symmetric matrice[J].Preprint series,2008(46):306-313.

[4] A Dilek (Güngör) Maden, KINKAR Ch Das, A Sinan Cevik. Sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph[J].Applied Mathematics and Computation,2013(219):5025-5032.

[5] SHU Jin-long, HONG Yuan, WEN Ren-kai. A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph[J].Linear Algebra and its Applications,2002(347):123-129.

[6] 谭尚旺，郭纪明，亓健.图的Laplacian矩阵和拟-Laplacian矩阵的谱半径[J].工程数学学报，2003,20(6):69-74.

[7] CHEN Yan.Properties of spectra of graphs and line graphs[J].Applied Mathematics a Journal of Chinese Universities, B,2002,17(3):371-376.

[8] HORN R A, JOHNSON C R. Matrix Analysis[M]. New York:Cambridge University Press,1985.

[9] SHU Jin-long, WU Ya-rong. Sharp upper bounds on the spectral radius of graphs[J]. Linear Algebra and its Applications,2004(377):241-248.

[10] VARGA R S. Matrix iterative analysis[M]. New Jersey: Prentice-Hall Engelwood Cliffe,1962.