Wiener指数，hyper-Wiener指数与图的哈密尔顿-连通性

舒阿秀，王礼想，于涛

(安庆师范大学数学与计算科学学院，安庆 246133)

设G=(V,E)为n阶简单连通图，其顶点集V=V(G)={v1,v2,…,vn}，边集E=E(G)为V的二元重集构成的集合.称E中元素{u,v}(u≠v)为G的边，边{u,v}简记为uv。记为G的补图，其顶点集V()=V(G)，边集E()为把G中所有不相邻顶点对连接起来得到的边的集合。顶点v的度dG(v)是指G中与v关联的边数，G的最小度记为δ(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)c∪(G2)c)c，即 在G1∪G2中添加由G1中每个顶点到G2中每个顶点的边所得的图。一条包含图G中所有顶点的路称为哈密尔顿路。如果图G中任意两顶点都一条哈密尔顿路相连，则称G是哈密尔顿-连通的。记clk(G)为G的闭包，它是指用下述方法从G中得到的一个图:反复连接G中度之和不小于k的不相邻的顶点对，直到没有这样的顶点对存在为止。

连通图G的Wiener指数，是与分子化合物的物理性质、化学性质相关性很高的拓扑指数，是1947年由 Wiener在[1]中首先提出的，记为W(G)，被定义为G中任意两个顶点的距离之和。

即:

图G的hyper-Wiener指数作为Wiener指数的推广，记为WW(G)，是 1993 年 Randi-ć在[2]中首先提出的，[2]中给出了无圈图hyper-Wiener的定义，进一步，1995年Klein等人在[3]中将hyper-Wiener的定义延伸到了所有的连通图中。图G的hyper-Wiener指数被定义为

决定一个给定的图是否是哈密尔顿的，是图论中的一类NP问题。近年来，随着研究的不断深入，学者们利用拓扑指数刻画图的哈密尔顿性，有了很大的突破，得到了很多充分或必要条件。在最小度δ≥k时，华洪波和宁博在[4]中利用图的Wiener指数，给出了一般连通图是哈密顿的和可迹的充分条件。蔡改香，余桂东等在[5]中利用图的hyper-Wiener指数给出一般连通图可迹的和哈密尔顿的充分条件。刘瑞芳等在[6]和[7]中，首先利用补图的Wiener指数，Harary指数给出一般图是可迹的和哈密尔顿的充分条件。我们根据以上文章得到启发，在[8]的相关条件的基础上，利用图及其补图的Wiener指数、hyper-Wiener指数，给出了具有最小度条件的连通图是哈密尔顿-连通的几个充分条件。

1 相关引理

引理1.1[8]设G为n阶连通图，n≥6k2-8k+5，δ≥k≥2，如果

则G是哈密尔顿-连通的，除非

2 主要结论

定理2.1设G为n阶连通图，n≥6k2-8k+5，δ≥k≥2，如果

则G是哈密尔顿-连通的，除非

证明 假设G不是哈密尔顿-连通的，通过引理 1.1，得

这与定理条件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)，则通过直接计算得

这与定理条件

故假设不成立，即G是哈密尔顿-连通的。

定理得证。

定理2.2 设G为n阶连通图，为n阶连通图，n≥6k2-8k+5，δ≥k≥2，如果

则G是哈密尔顿-连通的。

证明 假设G不是哈密尔顿-连通的，通过引理 1.1，得

这与定理条件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)

或cln+1(G)=Kk∨ (Kn-2k+1∪k-1)，则其补图不是连通图，与已知条件矛盾。

故假设不成立，即G是哈密尔顿-连通的。

定理得证。

定理2.3 设G为n阶连通图，n≥6k2-8k+5，δ≥k≥2，如果

则G是哈密尔顿-连通的，除非

证明 假设G不是哈密顿-连通的，通过引理1.1，得

这与定理条件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)或，由引理 1.1 知，G不是哈密尔顿—连通的。

定理得证。

定理2.4 设G为n阶连通图，为n阶连通图，n≥6k2-8k+5，δ≥k≥2，如果

则G是哈密尔顿-连通的。

证明 假设G不是哈密顿-连通的，通过引理1.1，得

这与定理条件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)或，则其补图不是连通图，与已知条件矛盾。

故假设不成立，即G是哈密尔顿-连通的。

定理得证。