图的一种加权邻接矩阵谱半径和能量的界_卢鹏丽.pdf

文章编号:1 6 7 3-5 1 9 6(2 0 2 3)0 1-0 1 4 4-0 8图的一种加权邻接矩阵谱半径和能量的界卢鹏丽*,薛小燕(兰州理工大学 计算机与通信学院,甘肃 兰州 7 3 0 0 5 0)摘要:图G的一种加权邻接矩阵记为Ad b(G)=(ad bi j)nn,若顶点vi和顶点vj相邻,则ad bi j=di+djdidj,反之ad bi j=0.给出图G的加权谱半径的上下界,并在此基础上给出加权谱半径的N o r d h a u s-G a d d u m-t y p e关系.得到了图G的加权能量的几个上下界,并在此基础上给出加权能量的N o r d h a u s-G a d d u m-t y p e关系.关键词:一种加权邻接矩阵;加权谱半径;加权能量;N o r d h a u s-G a d d u m-t y p e关系中图分类号:O 1 5 7.5;O 1 5 7.6 文献标志码:AB o u n d s f o r t h e s p e c t r a l r a d i u sa n de n e r g yo fak i n do fw e i g h t e da d j a c e n c ym a t r i xo fg r a p h sL UP e n g-l i,XU EX i a o-y a n(S c h o o l o fC o m p u t e ra n dC o mm u n i c a t i o n,L a n z h o uU n i v.o fT e c h.,L a n z h o u 7 3 0 0 5 0,C h i n a)A b s t r a c t:Ak i n do fw e i g h t e da d j a c e n c ym a t r i xo fg r a p hGi sd e n o t e db yAd b(G)=(ad bi j)nn,w h e r ead bi j=di+djdidji f t h ev e r t i c e svia n dvja r ea d j a c e n t,a n dad bi j=0o t h e r w i s e.I nt h i sp a p e r,s o m eu p p e ra n dl o w e rb o u n d so f t h ew e i g h t e ds p e c t r a l r a d i u so f g r a p hGa r e f i r s t o b t a i n e d,a n d t h e nt h eN o r d h a u s-G a d d u m-t y p er e l a t i o nf o rw e i g h t e ds p e c t r a l r a d i u s i sg i v e n.I na d d i t i o n,s e v e r a l u p p e r a n d l o w e rb o u n d s f o r t h ew e i g h t e de n e r g ya r eo b t a i n e d,t h e n,t h eN o r d h a u s-G a d d u m-t y p er e s u l t s f o r t h ew e i g h t e de n e r g ya r ep r e s e n t e d.K e yw o r d s:ak i n do fw e i g h t e da d j a c e n c ym a t r i x;w e i g h t e ds p e c t r a l r a d i u s;w e i g h t e de n e r g y;N o r d h a u s-G a d d u m-t y p er e l a t i o n 本文所考虑的所有图都是简单无向的.设G是包含顶 点 集V(G)=v1,v2,v3,vn 和 边 集E(G)=e1,e2,em的 图,即 图G为n=V(G)阶和m=E(G)条边的图.设di为顶点vi的度,图G中顶点的最大度和最小度分别为和.图G的补图记为G-且di为补图G-顶点vi的度.如果图G的每个顶点的度相同则称图G为正则图.图G的邻接矩阵记为A(G)=(ai j)nn,是一个nn维的矩阵,若顶点vi和顶点vj相邻,则ai j=1,反之ai j=0.A(G)的特征值记为12n,因为A(G)是n阶实对称矩阵,所以其特征值全为实数.A(G)最大特征值1称为图G的邻接谱半 收稿日期:2 0 2 1-1 2-2 1 基金项目:国家自然科学基金(1 1 3 6 1 0 3 3,1 1 8 6 1 0 4 5,6 2 1 6 2 0 4 0)通讯作者:卢鹏丽(1 9 7 3-),女,甘肃酒泉人,教授,博导.E m a i l:l u p e n g l i 8 81 6 3.c o m径.图G的能量记为=(G)=ni=1i.1 9 9 4年,Y a n g等1提出了图G的扩展邻接矩阵,表示为Ae x(G)=(ce xi j)nn,当图G中顶点vi和顶点vj相邻,则ce xi j=12didj+djdi,反之ce xi j=0.Ae x(G)的特征值记为12n.图G的扩展能 量 定 义 为e x=e x(G)=ni=1i.D a s2、G h o r b a n i等3、L i u等4、W a n g等5研究了图G的扩展邻接矩阵的谱半径和扩展能量的上下界.此外,关于各种矩阵的谱半径和能量的上下界的研究详见文献6-9.受扩展邻接矩阵的启发,X u等1 0提出了图G的一种新的加权邻接矩阵,并研究了其加权谱半径和加权能量的上下界.新提出的加权邻接矩阵定义为Ad b=Ad b(G)=(ad bi j)nn,若图G中顶点vi和顶点第4 9卷第1期2 0 2 3年2月兰 州 理 工 大 学 学 报J o u r n a l o fL a n z h o uU n i v e r s i t yo fT e c h n o l o g yV o l.4 9 N o.1F e b.2 0 2 3vj相邻,则ad bi j=di+djdidj,反之ad bi j=0.其加权邻接矩阵的特征值可以用12n表示,其中1为 其 谱 半 径,图G的 加 权 能 量 定 义 为d b=d b(G)=ni=1i.设f(G)是图的一个不变量,n是一个正整数.1 9 5 6年,N o r d h a u s和G a d d u m研究了关于图G色数及其补图G-色数的f(G)+f(G-)和f(G)f(G-)的上下界,在后面研究中,将图G及其补图G-的f(G)+f(G-)和f(G)f(G-)任意界称为N o r-d h a u s-G a d d u m-t y p e关系.A o u c h i c h e等1 1研 究 了N o r d h a u s-G a d d u m-t y p e关系在图的谱半径和能量上的应用.在此基础上,W a n g等5计算了扩展邻接矩阵的谱半径和能量的N o r d h a u s-G a d d u m-t y p e关系.拓扑指数作为图的不变量在数学和化学领域得到了广泛的应用.本文所使用的拓扑指数如下:图G的I S I指数1 0定义为I S I=I S I(G)=vivjE(G)didjdi+dj 图G的第一Z a g e r b指数M11 2,第二Z a g e r b指数M21 2,遗忘指数F1 2定义为M1=M1(G)=ni=1d2i=vivjE(G)di+djM2=M2(G)=vivjE(G)didjF=F(G)=ni=1d3i=vivjE(G)d2i+dj2 图G的修正第二Z a g e r b指数M*24,R a n d i c指数R4定义为M*2=M*2(G)=vivjE(G)1didjR=R(G)=vivjE(G)1didj 本文首先根据图G的一些不变量,如阶数n、边数m、最大度、最小度、一些拓扑指数等给出了加权谱半径的上下界.得到加权谱半径的N o r d h a u s-G a d d u m-t y p e关系,此外,还证明了图G的加权能量的上 下 界,进 一 步 得 到 加 权 能 量 的N o r d h a u s-G a d d u m-t y p e关系.1 引理给出一些必要的引理.引理15 若B是n阶实对称矩阵,其特征值为12n,对于任意一个向量xRn,x0有1xTB xxTx,等号成立当且仅当x是属于1的特征向量.引理21 0 设G是一个n阶图,则1)ni=1i=T r(Ad b)=0.2)ni=1(i)2=T r(A2d b)=2vivjE(G)di+djdidj2.引理31 0 设G是一个n阶图,则1=2=n当且仅当GKn或Gn2K2.引理41 3 设G是一个图,其大于、小于、等于0的特征值的个数分别为p、q、r,则r+m i np,q其中是图G的独立数.2 加权谱半径的上下界下面给出一些加权谱半径的上下界.为方便起见列出了下列不等式关系1 0:22di+djdidj222didjdi+djdidj2didjdi+dj2di+djdidjdi+dj2 定理1 设G是一个n阶m条边的图,其最大度和最小度分别为和,则1222mn(1)等式成立当且仅当G同构于n2K2.证明 易知:n21T r(A2d b)(2)由引理2得T r(A2d b)=2vivjE(G)di+djdidj22m222(3)因此18m 2n 4=222mn式(3)中的等式成立当且仅当d1=d2=dn=0.故图G是一个正则图且G不同构于Kn.式(2)中等式成立当且仅当1=2=n,541第1期 卢鹏丽等:图的一种加权邻接矩阵谱半径和能量的界 由引理3知G同构于n2K2或Kn.因此,综合可得式(1)中等式成立当且仅当G同构于n2K2.定理2 设G是一个n阶非空图,其最大度和最小度分别为和,则12 M1+45M*2n 3(+)(4)等式成立当且仅当图G是一个正则图.证明 设x=(x1,x2,xn)是Rn中的任意单位向量,则xTAd bx=2vivjE(G)di+djdidjxixj令x=1n,1n,1nTxTAd bx=2nvivjE(G)di+djdidj(5)若ai和bi是任意实数且满足h aibiH ai(i=1,2,n),则下列D i a z-M e t c a l f不等式成立1 4ni=1b2i+h Hni=1a2i(h+H)ni=1aibi等号成立当且仅当bi=h ai或bi=H ai.设bi=di+dj、ai=1didj、h=2(didj)、H=2(didj)代入上述不等式,则式(5)转化为xTAd bx=2nvivjE(G)di+djdidj2nvivjE(G)(di+dj)2+4(didj)2vivjE(G)1didj22didj(+)(6)因为2nvivjE(G)(di+dj)2+4(didj)2vivjE(G)1didj22didj(+)2n2vivjE(G)(di+dj)+4 52vivjE(G)1didj22(+)(7)则xTAd bx2n2 M1+4 52M*222(+)=2 M1+45M*2n 3(+)由引理1可得1xTAd bx2 M1+45M*2n 3(+)式(6)和式(7)中等式成立当且仅当d1=d2=dn=,则图G是一个正则图.进而,由1=xTAd bx可知x=1n,1n,1nT是对应于1的特征向量.综合可得式(4)中等式成立当且仅当图G是一个正则图.定理3 设G是一个n阶无孤立点的图,其最大度和最小度分别为和,则18 M*2-4Rn(8)等式成立当且仅当G是正则图.证明 设x=(x1,x2,xn)是Rn中的任意单位向量,则xTAd bx=2vivjE(G)di+djdidjxixj=2viv