Wiener指数，Hyper-Wiener指数，Harary指数与图哈密顿性

任丽芳，余桂东，李星星

（安庆师范大学数学与计算科学学院，安徽安庆246133）

设G=（V，E）为n阶简单连通图，其顶点集V=V(G)={v1,v2,…,vn}，边集 E=E(G)为 V的二元重集构成的集合。称E中元素{u,v}(u≠v)为G的边，边{u,v}简记为uv。顶点v的度dG(v)是指G中与v关联的边数，G的最小度记为δ。G中vi到vj最短路的长度，定义为vi与vj之间的距离，记作dG(vi,vj)。如果图G的每个顶点的度均为n-1，则称G为完全图，记作Kn。如果图G=(V,E)的顶点集V可以被划分为互不相交的子集X和Y，使得V=X⋃Y且任意边e={u,v}均满足u∈X,v∈Y或u∈Y,v∈X，则称G为二部图，记作G=(X,Y;E)。若 ||X =p， ||Y=q，并且X中所有顶点与Y中所有顶点都相邻，则称G=(X,Y;E)为完全二部图，记作Kp,q。设G1=(V1,E1)与G2=(V2,E2)是两个顶点不交的简单图，它们的并图为G1⋃G2=(V1⋃V2,E1⋃E2)，又记为 G1+G2；若 G1=…=Gk，用 kG1来表示G1⋃…⋃Gk；它们的联图为G1∨G2=即在G1⋃ G2中添加由G1中每个顶点到G2中每个顶点的边所得的图。一条包含图G中所有顶点的路称为哈密尔顿路。如果图G中任意两顶点都由一条哈密尔顿路相连，则称G是哈密尔顿-连通的。如果图G含有从任意一点出发的哈密顿路，则称G从任意一点出发都是可迹的。

连通图G的Wiener指数W(G)[1]，是指G中任意两个顶点的距离之和，即

图G的hyper-Wiener指数[2-3]作为Wiener指数的推广，记为WW(G)，

这与定理条件WW(G)

若G∈NP，由引理2知，G不是从任意一点2出发都是可迹的。

定理6 设G为n阶连通图，n≥5，δ≥2，如果H(G)≥则G是从任意一点出发都是可迹的，除非G∈NP2={K2∨(Kn-4+

证明 假设G不是从任意一点出发都是可迹的，由引理2可得

这与定理条件H(G)≥若G∈NP2，由引理2知，G不是从任意一点出发都是可迹的。

[1]WIENER H.Structural determination of paraffin boiling points[J].Journal of theAmerican Chemical Society,1947,69(1):17.

[2]RANDIC M.Novel molecular descriptor for structure-property studies[J].Chemical Physics Letters,1993,211(4-5):478-483.

[3]KLEIN D J,LUKOVITS I,GUTMAN I.On the definition of the hyper-Wiener index for cycle-containing structures[J].Journal of Chemical Information&Modeling,1995,35(1):50-52.

[4]PLAVCHECKSIC D,NIKOLIC S,TRINAJSTIC N,et al.On the Harary index for the characterization of chemical graphs[J].Math Chem,1993,12(1):235-250.

[5]IVANCIUC O,BALABAN T S,BALABAN A T.Reciprocal distance matrix,related local vertex invari-ants and topological indices[J].Math Chem,1993,12(1):309-318.

[6]ZHOU Q,WANG L.Some sufficient spectral conditions on Hamilton-connected and traceable graphs[J].Linear and MultilinearAlgebra,2017,65(2):224-234.