基于Wiener指数和Harary指数的泛圈图的充分条件.pdf

DOI:10.159606093.2023.03.014Operations Research TransactionsSep.,2023Vol.27No.32023年9 月第2 7 卷第3 期运筹学学报基于Wiener指数和Ha指数的泛圈图的充分条件*贾会才1,宋宏业2摘要令G是一个简单连通图。若包含长度为3到n的所有圈，则称图G是泛圈的。基于Wiener指数、Harary指数、距离谱半径和Harary谱半径，提供了图G是泛圈图的充分条件，从而建立了图的代数性质与结构性质之间的紧密联系。关键词泛圈图，Wiener指数，Harary指数，距离谱半径，Harary谱半径中图分类号02212010数学分类号05C50,05C12Suficient conditions on Wiener index andHarary index for pancyclic graphs*JIA Huicail,tSONG Hongye?Abstract Let G be a simple and connected graph.A graph G is pancyclic if itcontains all possible cycles with length from three to the number of vertices.In thispaper,we provide sufficient conditions for a graph to be pancyclic in terms of the Wienerindex,the Harary index,the distance spectral radius and the Harary spectral radius of agraph,respectively.These results establish the relationship between algebraic propertiesand structural properties of graphs.Keywords pancyclic graphs,Wiener index,Harary index,distance spectral radius,Harary spectral radiusChinese Library Classification O2212010 Mathematics Subject Classification05C50,05C12本文所讨论的图都是简单无向连通图。令G是一个顶点集V(G)=【u 1,U 2，U n)和边集为E(G)的连通图。用dc(u)表示顶点的度。设G是图G的补图。包含长度为3到n的所有圈的连通图称为泛圈图。设D(G)表示图G的距离矩阵，pP(G)表示图G的距离谱半径。分子图的Wiener指数最早由Wiener在1 9 47 年的文献1 中引进并定义为连通图G的所有点对的距离和,也就是W(G)=Zu,veV(G)dc(u,u)。设 D;(G)和 D(G)分别表示 D(G)的第i行的收稿日期：2 0 2 0-0 4-0 4*基金项目：国家自然科学基金（Nos.11701148，1 1 8 0 1 1 44)1.河南工程学院理学院，河南郑州451 1 9 1；College of Sciences，H e n a n U n i v e r s i t y o f E n g i n e e r i n g，Zhengzhou 451191,Henan,China2.北京第二外国语学院基础科学部，北京1 0 0 0 2 4；Ministry of Basic Science，Be i j i n g In t e r n a t i o n a lStudies University,Beijing 100024,China十通信作者E-mail:17027卷贾会才，宋宏业行和以及对应于顶点的行和。则1n1W(G)=D(G):D;(G)。22UEV(G)1图G的Harary指数H(G)是1 9 9 3年由Ivanciuc等在文献2 和Plavsic等在文献3中刻画分子图时各自独立引进的。Harary指数定义为连通图的所有点对的距离的倒数的和，即H(C-V，注意到任何不连通图C中两个不同分支的任意两1个顶点间距离是无穷大，所以它的倒数是0。因此，我们能定义不连通图G的Harary指数如下：H(G)=H(G),其中G1,G2,G为G的连通分支。我们经常用D:(G)或D()来表示2 ev(C)ad，则1H(G)=21nDu.(G)=1D;(G)。2UEV(G)1图G的Harary矩阵RD(G)，最开始在文献2 中被称为倒数距离矩阵。它是一个nn矩阵，且当ij时，其（i,i)-元素等于击，否则为0。图G的Harary谱半径是矩阵RD(G）的最大特征值，用p*(G）来表示。注意到在任意一个不连通图G中，p*(G）=max(p*(Gi)/1 i k)。近些年，寻找图的各种谱半径、Wiener指数、Harary指数与图的一些重要结构性质之间的关系引起了学者们的广泛关注。文献4给出了哈密顿图和可迹图的基于Wiener指数和Harary指数的充分条件。最近，Yu等在文献5中给出了基于图的边数、谱半径、无符号Laplacian谱半径的图的泛圈性的一些充分条件。受此启发，本文分别讨论了基于Wiener指数、Harary指数、距离谱半径和Harary谱半径的图的泛圈性的充分条件，丰富和拓展了文献中的研究结果。1主要引理和预备知识设 NP=K2 V(Kn-4+2K1),Ks V6K1,K3 V(K2+3K1),K3 V(K1,4+Ki),K3 V(K1,3+K2),(K2 V2K1)V5K1,K4 V5K1,K1,2 V4K1,K2 V(K1,3+K1),K3 V4K1)。引理1 5】设连通，顶点数为n5，边数为m，最小度为2。如果m()+4,那么 G 是泛圈图除非 GNP,，或者 G 是二部图。引理 2 6 设是n阶连通图，则pp(C)2W(，且等号成立当且仅当D(C）的n行和都相等。引理 34设G是n阶连通图，则p*(G)2H(C)，且等号成立当且仅当RD(G）的n行和都相等。引理4设G是n阶二部图，则W(G)n+3n-142证明设G是n阶二部图，其顶点集被划分为两个不交独立集Vi和V2，其中Vil=a(1an-1)和|V2l=n-a。171基于Wiener指数和Harary指数的泛圈图的充分条件3期1W(G)D;(G)12iEV(G)(d+3(n-d)2(-1)+)Z(d;+3(-d)+2(n=a-1)2itVijV2(3n-a-2-2d;)+(2n+-2-2d,)2iEVijEV2-?+na+n?-n-djiEV(G)=-+na+n-n-2m2-+na+n-n-2a(n-a)=-na+n-n3n2-4n4O通过计算可得3n24nn+3n-14,则 W(G)n+3n-14422引理5设G是n阶二部图,其中n8,则H(G)5n-23n+282(n-1)证明设G是二部图，顶点数为n8，且顶点集被划分为两个不交独立集Vi和V2。令 Vil=(1 n-1),V2l=n-a。情形1 G不是完全二部图，则2D.(C)n1H(G)1211dc(u)-1-dc()23VEV(G)1n 一12dc(u)233VEV(G)n(n-1)1dc(u)63UEV(G)n(n-1(n-1-dc(u)63UEV(G)n(n-1)2m23n(n-1)2a(n13a24a-4na+3n-3n62n22-3n6通过计算可得2n2-3n5ng元2 3n+28,则 H(G)5ng23n+28,其中 n 4。62(n-1)2(n-1)27卷172贾会才，宋宏业情形2G是完全二部图,则 G=Ka,n-a,n1H(G)2D:(G)12=1Z(a-1)+）Z(n-1)UEV1UEV2a2-na+n2n2-2n4通过计算，可得n-2n5n=23n+28,其中 n8。那么 H(G)5n-23n+2842(n-1)2(n-1)O2主要结论本节基于图G和其补图G的Wiener指数、Harary指数、距离谱半径和Harary谱半径给出泛圈图的一些充分条件。定理1 设G连通，顶点数为n5,最小度为2。如果W(G)n 2 3n-1 4,那么2G是泛圈图,除非 GENP。证明假定G不是泛圈图。则n1W(G)D;(G)121(d:+(-1-d)121n1(2(n-1)-d)21n(n-1)-m。注意到 W(G)+-4,n-623m-28,我们有mn-7ma+24n-28=(n一2)+4。根据引理1,我2(n-2)们可得GENP，或者G是二部图。注意到对于所有的GENP,G不连通。如果G是完全二部图，则G也不连通。因此G是非完全二部图。定理证毕。定理3设G连通,顶点数为n5,最小度为2。如果H(G)n-3n7,那么2G是泛圈图,除非GENP。证明假定G不是泛圈图。则2D(C)1H(G)2=1n1(d;+(n-1-d;)221n(n一m42O注意到 H(G)2-+7，我们有n-3n+7-=（)+4，根据引理1.我们22可得 GeNP，或者G是二部图。计算可知，对于所有的GENP,H(G)一+7。如果2G是二部图,其顶点集被划分成两个不交的独立集Vi 和V2,其中 IVil=(1n-1),IV2l=n-a。我们有1H(G)D;(G)2iEV(G)(ZD:(C)+)1ZD;(G)2ieVijEV2(d+(n-a-d)+(-1)+(d;+(a-d)+(n-1)3itVijEV22a2-2na+3n-3n1di1213iEV(G)2a2-2na+3n-3n2m1232a2-2na+3n-3n2a(n-a)123-2a+2na+n 3n2n一2n48注意到3n2_2n-3n7,与题设矛盾。因此GENP。8217427卷贾会才，宋宏业定理4设G连通，顶点数为n8,最小度为2。如果H(G)5n-23n+282(n-1)那么G是泛圈图,除非GKsV6K1,K(K2+3K1),K(K1,4+K1),K3(K1,3+K2),(K2 V2K1)V5K1,K4 V5Ki)。证明假定G不是泛圈图。则nH(G)2D:(C)12111da(u)+(n-1-dc(u)2nvEV(G)1n一21+dc(u)2n一vEV(G)nn-2(n-1-dc(u)22(n-1)VEV(G)n(n-1)n-2dc(u)22(n-1)vEV(G)n(n-1)n一2m。2n-1注意到 H(G)5n元2 3n+28,我们有2(n-1)n(n-1)25n 23n+28n-2)m+4。2(n-2)2(n-2)2根据引理1,可得GENP，或者G是二部图。如果G是二部图，根据引理5,对n8,我们有H(C)52+2，与题设矛盾。注意到当n8时，我们有2(n-1n2n85n2-23n+28H(K2 V(Kn-4+2K1)42(n-1)然而，通过直接计算，对于所有的GENPK2V(Kn-4+2K1),均有H(G)5n-23n+282(n-1)满足题设条件。最后因为图K1,2V4K1,K2V(K1,3+K1),K3V4Ki的点数均为7。所以GEKsV6K1,K3V(K2+3K1),K3V(K1,4+K1),KV(K1,3+K2),(K2V2K1)V5K1,K4V5K1)。结论成立。下面我们给出基于距离谱半径和Harary谱半径的泛圈图充分条件。定理5设G连通，顶点数为n5,最小度为2。如果pP(G)n+3-，那么G是泛圈图,除非GEK2V(K1,3+Ki),K34Ki)。证明假定G不是泛圈图。根据引理2 和定理1 的证明，我们有2W(G)2pP(G)=(n(n-1)-m)=2(n-1)-=m。nn由于p(G)n+3-，我们有m(=)+4。根据引理1,GNP,或者G是二部图。如果G是二部图，由引理4的证明可得W(G)3n-4n,则42W(G)3n-414pP(G)n+3-n2n175基于Wiener指数和Hararyy指数的泛圈图的充分条件3期与题设矛盾。对于 G=K2(Kn-4+2Ki),设X=(a1,2,an)T 是图 G的对应于 p(G)的特征向量,其中(1 in4)对应于度为n-3的点，a;(n-3jn-2)对应于度为2的点，(n-1ln)对应于度为n-1的点。不失一般性，令:=ai,1in4;y:=j,n-1jn;z:=ai,n-1ln。因为 pPx=D(G)X,所以pPa=(n-5)+4y+2z,pPy=2(n-4)c+2y+2z,pDz=(n-4)+2y+z。因此pP(K2V(Kn-4+2K1)是方程(pP)3-(n-2)(pD)2-(7n-23)(pD)-2(n-3)=0的最大根。设f(a)=3-(n-2)-(7-23)2(n-3)。当5时,f(n+3-)=2n+16n6 476+2156 2744nn3n+31，与已知条件矛盾。通过计算，我们有下面的表1。表1 一些图的距离谱半径GpP(G)n+3-14nK5V6K113.24512.727K3 V(K2+3K1)9.59479.25K3 V(K1,4+K1)10.834110.444K3 V(K1,3+K2)10.767 210.444(K2 V2K1)V5K110.762 410.444K4V5K110.632 510.444K1,2 V4K18.27368K2 V(K1,3+K1)88K3V4K188由表1 得知,GEK2V(K1,3+K1),K3V4Ki)。结论证毕。定理6 设G连通,顶点数为n8,最小度为2。如果p*(G)5n23n+28,那n(n-1)么G是泛圈图。证明假定G不是泛圈图。通过引理3和定理4的证明，我们有2H(G)2(n-2)mp*(G)n一1nn(n-1)由于*(G)n+2，所以m(=2)+4。根据引理1 可得 GNP,或者 G是二部n(n-1)图。对于G=K2V(Kn-4+2K1)，设X=(a1,C2,，a n)T 是对应于p*(G)的特征向量,其中i（1 i n-4)是对应于度为的点，(n-3j-2)是对应于度为n317627卷贾会才，宋宏业的点，(n-1ln）是对应于度为的点。不失一般性，令:=i,1in4;y:=aj,n-1jn;z:=t,n-1ln。因为 p*(G)X=RD(G)X,所以p*a=(n-5)+2y+0z,p*y=(n-4)c+y+0z。因此p*(K2V(Kn-4+2K1)是方程星2(p*)2-(n-3)p*+11-3n=0的最大根。则当n5时，我们有p*(K2V(Kn-4+2K)=n-3+Vn18m-75n-23n+28，不满足题设4n(n-1)条件。经过计算，我们有下面的表2。表2 一些图的补图的Harary谱半径p*(G)5n_23n28n(n-1)KsV6K153.4546K3 V(K2+3K1)4.06632.928 6K3 V(K1,4+K1)4.411 53.1389K3 V(K1,3+K2)4.54553.1389(K2 V2K1)V5K143.138 9K4V5K143.1389K1,2V4K132.667K2 V(K1,3+K1)3.45752.667K3V4Ki32.667显然,对于 G E NIP,p*(G)5n-23n+28,与题设矛盾。n(n-1)如果G是二部图，顶点数n8，直顶点集被划分为两个不交的独立集Vi和V2Vi/=a(1 a n-1),/V2l=n-a。情形1 G不是完全二部图。通过引理3和引理5的证明，我们有p*(G)2n-35n-23n+28,其中 n4,与题设矛盾。3n(n-1)情形G是完全二部图。则=K a,n-a。通过引理3和引理5的证明，我们有p*(G)n-25nm-23n+28，其中n8，与题设矛盾。定理6 证毕。2n(n-1)3结论和展望哈密顿问题是图论中著名的NP困难问题，寻找好的刻画一直是图论研究者高度关注的问题。由于图的谱能很好地反映图的结构性质且便于计算，自2 0 1 0 年以来，图的哈密顿相关性质的谱刻画问题成为了当今图谱理论研究的一个前沿热点问题。不论是对稠密图，还是对稀疏图，证明哈密顿相关性质（包括高哈密顿性以及点边泛圈性）的各种特征值充分条件都具有相当重要的意义。随着图谱理论研究的纵深发展，关于图的谱参数与结构参数的研究仍然有许多历史遗留难题和猜想呕待解决，而且围绕图的哈密顿相关性质的谱刻画问题，仍然有诸多遗留问题。比如关于图的泛圈性的谱刻画研究，目前研究结果很少，我们将继续探讨泛圈图的谱刻画问题。1773期基于Wiener指数和Harary指数的泛圈图的充分条件参考文献1 Wiener H.Structural determination of paraffin boiling points J.Journal of the AmericanChemical Society,1947,69:17-20.2 Ivanciuc O,Balaban T,Balaban A.Reciprocal distance matrix,related local vertex invariantsand topological indices J.Journal of Mathematical Chemistry,1993,12:309-31.3 Plavsic D,Nikolic S,Trinajstic N,et al.On the Harary index for the characterization ofchemical graphs J.Journal of Mathematical Chemistry,1993,12:235-250.4 Liu R F,Du X,Jia H C.Some observations on Harary index and traceable graphs J.MATCHCommunications in Mathematical and in Computer Chemistry,2017,77:195-208.5 Yu G D,Yu T,Shu A X,et al.Some sufficient conditions on pancyclic graphs J.2018,arXiv:1809.09897v1.6 Indulal G.Sharp bounds on the distance spectral radius and the distance energy of graphs J.Linear Algebra and Its Applications,2009,430:106-113.