路矩阵相关谱半径和路谱展的界及其应用
2023-02-15卢鹏丽栾睿
卢鹏丽, 栾睿
(兰州理工大学 计算机与通信学院,甘肃 兰州 730050)
1 基本概念和主要引理
引理2[14]n阶连通图G只有2个不同的路特征值当且仅当G是k-连通且k-正则图,2≤k≤n-1。
引理3[15]设Q为对应于方阵A的等价划分的商矩阵,则A的谱包含Q的谱。
2 图的路谱半径和路无符号拉普拉斯谱半径的界
等式成立当且仅当G为路传递正则图。
定理3若G为简单连通图,则:
等式成立当且仅当G为路传递正则图。
证明:因为PQ(G)=TrP(G)+P(G),通过简单计算可得
则
rvi((PQ(G))2)=rvi((TrP)2+TrPP+PTrP+P2)=
rvi(TrP(TrP+P))+rvi(PTrP)+rvi(P2)=
定理4若G为简单连通图,则:
等式成立当且仅当G为路传递正则图。
证明:证明过程同定理3。
(1)
等式成立当且仅当G为路传递正则图。
3 路谱展的下界
定理6设图G为n阶连通图,则:
(2)
等式成立当且仅当G为k-连通且k-正则图。
当且仅当ρ2=ρ3=…=ρn时式(2)取等,即当且仅当G有2个完全不同的路特征值。利用引理2,可以得出G为k-连通且k-正则图。反之,若G为k-连通且k-正则图,可通过直接计算可证。该定理得证。
定理7设图G为n阶连通图,则:
等式成立当且仅当G为k-连通且k-正则图。
证明:因为
(3)
当且仅当ρ2=ρ3=…=ρn时式(3)取等,即当且仅当G有2个完全不同的路特征值。利用引理2,可以得出G是k-连通且k-正则图。反之,若G为k-连通且k-正则图,可通过直接计算可证。该定理得证。
推论1设图G为n阶连通图,其路Wiener指数为PW(G),则:
PS(G)≥
等式成立当且仅当G为k-连通且k-正则图。
证明:根据定理1和定理7可证。
定理8设图G为n阶连通图,则:
4 完全r-部图的路谱和路(无符号)拉普拉斯谱
SpecP(Kp1,p2,…,pr)=((p1-n)p1-1,(p2-n)p2-1,…,
(pr-n)pr-1,1,2,…,n)
的特征值。
证明:给顶点集V(Kp1,p2,…,pr)一个划分π:V(Kp1,p2,…,pr)=V1∪V2∪…∪Vr,其中Vi为第i部中的顶点,则完全r-部图Kp1,p2,…,pr的路矩阵P(Kp1,p2,…,pr)的分块矩阵表示为:
则这个矩阵的n-r个特征值为:(p1-n)p1-1,(p2-n)p2-1,…,(pr-n)pr-1。因为π为图Kp1,p2,…,pr的路等价划分,所以其对应的商矩阵Q3由式(4)给出,计算det(xI-Q3),可得Q3的特征值,由引理3可知,即为P(Kp1,p2,…,pr)的剩余r个特征值。
推论2令Kp,p,…,p为特殊的完全r-部图,其中r≥2,n=rp,则 SpecP(Kp,p,…,p)=((p-n)n-1,((n-p)(n-1))1),PE(Kp,p,…,p)=2(n-p)(n-1)。
证明:根据定理9可证。
其中ζ1,ζ2,…,ζr为矩阵
的特征值。
证明:
其中:
(n-p3)Jp3×p3,…,
证明过程同定理9。
推论3令Kp,p,…,p为特殊的完全r-部图,其中r≥2,n=rp,则 SpecPL(Kp,p,…,p)=((n(n-p))n-1,0),PLE(Kp,p,…,p)=2(n-p) ·(n-1)。
证明:根据定理10可证。
其中ξ1,ξ2,…,ξr为矩阵
的特征值。
其中:
⋮
证明:
其中:
⋮
证明过程同定理9。
推论4令Kp,p,…,p为特殊的完全r-部图,其中r≥2,n=rp,则 SpecPQ(Kp,p,…,p)=(((n-2)(n-p))n-1,(2(n-1)(n-p))1),PSLE(Kp,p,…,p)=2(n-p)(n-1)。
证明:根据定理11可证。
5 结论
1)得到了任意图的路谱半径和路(无符号)拉普拉斯谱半径的界。
2)定义了路谱展的概念并得到其下界。
3)计算了完全r-部图的路谱和路(无符号)拉普拉斯谱及其能量,拓宽了路谱的研究范围。