路矩阵相关谱半径和路谱展的界及其应用_卢鹏丽.pdf

第 44 卷第 2 期2023 年 2 月哈 尔 滨 工 程 大 学 学 报Journal of Harbin Engineering UniversityVol.44.2Feb.2023路矩阵相关谱半径和路谱展的界及其应用卢鹏丽,栾睿(兰州理工大学 计算机与通信学院,甘肃 兰州 730050)摘 要:由于图谱能够很好地反映图的结构性质且便于计算,本文通过图的矩阵,建立图谱与图的拓扑性质之间的联系,更好地反应图的结构和研究图的相关性质;利用矩阵论和图论的理论和方法,证明路谱半径的下界和路无符号拉普拉斯谱半径的上下界;定义路谱展并得到其上下界;最后作为应用,研究完全 r-部图的路谱、路拉普拉斯谱和路无符号拉普拉斯谱并得到了图 Kp,p,p的相关能量。关键词:路矩阵;路谱展;路谱半径;能量;路无符号拉普拉斯谱半径;完全 r-部图;路谱;路(无符号)拉普拉斯谱DOI:10.11990/jheu.202106018网络出版地址:https:/ 文献标志码:A 文章编号:1006-7043(2023)02-0251-06Bounds of correlation spectrum radius of path matrix and path spectrum spread and their applicationsLU Pengli,LUAN Rui(School of Computer and Communication,Lanzhou University of Technology,Lanzhou 730050,China)Abstract:The graph spectrum can well reflect the structural properties of graphs and is easy to calculate.In this paper,the relationship between graph spectrum and topological properties of graph is established by the matrix of graph,so as to better reflect the structure of graph and study related properties of the graph.Using the theory and method of matrix theory and graph theory,we prove the lower bound of the path spectrum radius and the upper and lower bounds of the path signless Laplacian spectrum radius.We define the path spectrum spread and get the upper and lower bounds.Finally,as an application,we study the complete r-partite graph,get the path spectrum,path Laplacian spectrum and path signless Laplacian spectrum and related energy of Kp,p,p.Keywords:path matrix;path spectrum spread;path spectrum radius;energy;path signless Laplacian spectrum ra-dius;complete r-partite graph;path spectrum;path(signless)Laplacian spectrum 收稿日期:2021-06-18.网络出版日期:2022-11-03.基金项目:国家自然科学基金项目(11861045,62162040).作者简介:卢鹏丽,女,教授,博士生导师.通信作者:卢鹏丽,E-mail:lupengli88 .代数图论是采用代数方法解决图论的问题,图谱理论是其中一个非常重要的研究领域。图谱理论的研究是以邻接矩阵、(无符号)拉普拉斯矩阵、距离矩阵、距离(无符号)拉普拉斯矩阵等图的矩阵为主要研究对象,通过将图转化成相应矩阵,应用矩阵的特征值和特征向量来建立图的拓扑结构和特征值、特征向量等之间的联系。图谱重要的理论意义及广泛的应用价值使得它不仅与数学分支有着密切的联系,而且在量子化学、统计力学、通信网络及信息科学中也有一系列重要的应用;另外,图的谱理论也促进和丰富了图论和组合数学本身的研究,已经成为组合矩阵理论研究的一个重要的方面。Patekar等1定义了路矩阵的概念,目前学者们对路矩阵的研究相对较少,主要是路谱半径和路谱能量方面的研究;Gutman2研究了路矩阵的基本性质,得到了一些简单图的路谱,如树、圈图、完全图、完全二部图,提出了路谱能量的概念并给出了关于单圈图和双圈图的路谱半径和路谱能量的猜想;Akbari 等3研究了任意图的路谱能量的极值问题,解决了单圈图的路谱能量的极值问题,得到了 k-连通且 k-正则图的路谱半径和路谱能量;Ilic等4得到了单圈图的路谱半径和路谱能量;Akbari 等5研究了双圈图的路谱能量并得到上下界。更多关于谱半径及相关谱能量的研究参见文献6-11。本文研究了一般图的路谱半径下界和路无符号拉普拉斯谱半径的上下界,受距离谱展的启发,定义了路谱展的概念并哈 尔 滨 工 程 大 学 学 报第 44 卷求得其下界,得到了完全 r-部图的路谱、路(无符号)拉普拉斯谱及其特殊完全 r-部图的相关谱能量。1 基本概念和主要引理 设图 G=(V(G),E(G)为 n 个顶点的简单连通图,其中顶点集 V(G)=v1,v2,vn,E(G)为边集。用 P(G)=(pij)nn表示图 G 的 n n 阶路矩阵,其中 pij表示图 G 中任意顶点 vi,vj V(G)之间内部顶点不相交(即不重复)的最大路径数目 p(vi,vj),其特征值记为(G)=)1 2 n,因为路矩阵 P(G)是实对称矩阵,其特征值都为实数,特征值的集合为图 G 的路谱 SpecP(G)=(1,2,n),路谱能量2定义为 PE(G)=ni=1|i|,路矩阵最大的特征值(G)为 P(G)的路谱半径。受距离谱展12的启发,定义路谱展(path spec-trum spread)为 PS(G)=1-n。图 G 的路传递矩阵用 TrP(G)表示,即 TrP(G)=diag(TrP1,TrP2,TrPn),其中 TrPi表示顶点 vi到 G 中其他顶点路径数目之和 TrPi=TrP(vi)=vjV(G)p(vi,vj)。如果对任意顶点 viV(G),都有 TrPi=k,则称图 G 为 k-路传递正则图。路传递度序列记为 TrP1,TrP2,TrPn,顶点 vi的第二路传递度 TPi为 TPi=nj=1pijTrPj,第二路传递度序列表示为 TP1,TP2,TPn。图的路拉普拉斯矩阵和路无符号拉普拉斯矩阵,分别为 PL(G)=TrP(G)-P(G)和 PQ(G)=TrP(G)+P(G),相应的特征值分别记为(L(G)=)L1 L2 Ln,(Q(G)=)Q1 Q2 Qn,相应的特征值的集合分别为图 G 的路拉普拉斯谱和路无符号拉普拉斯谱,即 SpecPL(G)=(L1,L2,Ln)和 SpecPQ(G)=(Q1,Q2,Qn)。平均路传递度 tP(G)为 tP(G)=1nni=1TrP(vi),路拉普拉斯谱能量和路无符号拉普拉斯谱能量,分别为 PLE(G)=ni=1Li-tP(G)和PSLE(G)=ni=1Qi-tP(G)。图 G 的路 Wiener 指数 PW(G)表示 G 中所有无序顶点对之间的路径数目之和,即 PW(G)=12vi,vjV(G)p(vi,vj)。引理 113 若 A 为 n n 阶的非负矩阵,其谱半 径 为(A),行 和 分 别 为 r1(A),r2(A),rn(A),则 min1inri(A)(A)max1inri(A),当且仅当 A 的行和都相等时,2 个等式都成立。引理214n 阶连通图 G 只有2 个不同的路特征值当且仅当 G 是 k-连通且 k-正则图,2 k n-1。引理 315设 Q 为对应于方阵 A 的等价划分的商矩阵,则 A 的谱包含 Q 的谱。2 图的路谱半径和路无符号拉普拉斯谱半径的界 定理 1 设图 G 为 n 阶连通图,其路 Wiener 指数为 PW(G),则(G)2PW(G)n,等式成立当且仅当 G 为路传递正则图。证明:令 x=1n(1,1,1),图 G 的路矩阵为P,由 Raleigh 原理可得:(G)xPxTxxT=1n(TrP1,TrP2,TrPn)1n(1,1,1)T=ni=1TrPin=2PW(G)n假设图 G 是路传递正则图,则路矩阵 P 的行和均为常数 k 且 2PW(G)=nk,由 Frobenius 定理16,k 为最大单特征值,则(G)=k=nkn=2PW(G)n,因此等式成立。反之,如果等式成立,则 x 为对应特征值(G)的特征向量,即 Px=(G)x。所以对于所有的 i,TrPi=(G),由于 TrPi是一个整数,因此 G 是路传递正则图。因此该定理得证。定理 2 设图 G 为 n 阶连通图,其路传递度序列为 TrP1,TrP2,TrPn,则:(G)(TrP1)2+(TrP2)2+(TrPn)2n,等式成立当且仅当 G 为路传递正则图。证明:令图 G 的路矩阵为 P,X=(x1,x2,xn)为 P 的对应于(G)的正单位 Perron 向量。取 C=1n(1,1,1),则 C 是单位正向量,因此:(G)=2(G)=XP2XTCP2CT。现有 CP=1n(1,1,1)P=1n(TrP1,TrP2,TrPn),则 CP2CT=CP(CP)T=1nni=1(TrPi)2,所以(G)CP2CT=1nni=1(TrPi)2。252第 2 期卢鹏丽,等:路矩阵相关谱半径和路谱展的界及其应用假设 G 是路传递正则图,则对于所有的 i,有TrPi=k,因此由 Frobenius 定理可知,k 是 P 的最大单特征值,又有(G)=k=nk2n=1nni=1(TrPi)2,因此等式成立。反之,如果等式成立,则 C 为对应特征值(G)的特征向量,证明如定理 1,得到 G 为路传递正则图。该定理得证。图 G 的最大路传递度和最小路传递度分别用TrPmax和 TrPmin表示,TPmax和 TPmin分别表示图 G 的最大第二路传递度和最小第二路传递度。定理 3 若 G 为简单连通图,则:Q(G)TrPmax+(TrPmax)2+8TPmax2,等式成立当且仅当 G 为路传递正则图。证明:因为 PQ(G)=TrP(G)+P(G),通过简单计算可得 rvi(PQ(G)=2TrPi,rvi(P2)=rvi(PTrP)=TPi。则rvi(PQ(G)2)=rvi(TrP)2+TrPP+PTrP+P2)=rvi(TrP(TrP+P)+rvi(PTrP)+rvi(P2)=TrPirvi(PQ(G)+2TPi TrPmaxrvi(PQ(G)+2TPmax即 rvi(PQ(G)2-TrPmaxPQ(G)2TPmax。由引理 1可得(Q(G)2-TrPmaxQ(G)-2TPmax 0。对任意的顶点 vi,当 TrPi=TrPmax,TPi=TPmax时,不等式取等,即当图 G 为路传递正则图时取等;反之,当图 G 为路传递正则图时,不等式取等。定理 4 若 G 为简单连通图,则:Q(G)TrPmin+(TrPmin)2+8TPmin2,等式成立当且仅当 G 为路传递正则图。证明:证明过程同定理 3。定理 5 若 G 为 n 阶简单连通图,其路传递度序列为 TrP1,TrP2,TrPn,则:Q(G)2ni=1(TrPi)2