梅培林，蔡改香

（安庆师范大学数理学院，安徽安庆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之间的距离。如果图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)。定义是完全图Kn,n通过删除它子图Kt-1,n-t的所有边得到的图，其中2 ≤t ≤(n +1)/2。如果任意两个不同部分的顶点可以通过哈密顿路连接，那么该二部图为弱哈密顿连通图。如果图G的一条路或一个圈经过所有的顶点，那么称之为哈密顿路和哈密顿圈。如果G有哈密顿路或者哈密顿圈，则称G是可迹图或者哈密顿图。如果任意两个顶点都能由一条哈密顿路相连，则称G是哈密顿连通的。

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

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

图G 的Harary 指数是化学图论中一个非常有用的拓扑指数，记为H(G)，是1993 年由Plavchecksic等[4]和Ivanciuc等[5]首先提出的。连通图G的Harary指数被定义为

最近，拓扑指数在很多方面都有运用，文献[6]给出了Wiener指数、Harary指数关于哈密顿图的一些充分条件；然后文献[7]进一步给出了Wiener指数、Harary指数、hype-Wiener指数关于图的哈密顿性的一些充分条件。但是弱哈密顿连通图的相关拓扑指数，还没人进行研究，本文利用Wiener指数、hyper-Wiener指数和Harary指数给出弱哈密顿连通图的一些充分条件。

1 相关引理

引理1设G是连通的平衡二部图则

证明（1）设则

等号成立当且仅当如果x,y属于不同部分，d(x,y)≤3；x,y属于同一部分，d(x,y)=2，即引理得证。

（2）设G=[ X ,Y ]，X={ x1,x2,…,xn},Y ={ y1,y2,…,yn}，则

等号成立当且仅当如果x,y属于不同部分，d(x,y)≤3，x,y属于同一部分，d(x,y)=2，即引理得证。

引理2 设G是连通的平衡二部图，|X |= |Y |=n，WW(G)≥9n2-3n-5e(G)，对于图G中任意两个点x,y，如果x,y属于不同部分，等号成立当且仅当d(x,y)≤3；如果x,y属于同一部分，等号成立当且仅当d(x,y)=2。

证明设G=[X,Y]，X={x1,x2,…,xn},Y={y1,y2,…,yn}，则

等号成立当且仅当如果x,y属于不同部分，d(x,y)≤3；x,y属于同一部分，那么d(x,y)=2。

引理3[8]设G(X,Y,E)是一个平衡二部图，|X|= |Y|=n。如果δ(G)≥k≥1，n≥2k，e(G)＞n(n-k)+k(k+1)，则G是弱哈密顿连通的。

2 主要结论

定理1设G(X,Y,E)是一个连通的平衡二部图，|X|= |Y|=n，δ(G)≥k≥2。如果n≥2k+1，，则G是弱哈密顿连通的。

证明通过引理1 可得则

定理2设G(X,Y,E)是一个连通的平衡二部图如果n≥2k+1，，则G是弱哈密顿连通图。

证明通过引理1 可得如果则

定理3设G(X,Y,E)是一个连通的平衡二部图，|X|= |Y|=n，δ(G)≥k≥2。如果n≥2k+1，则G是弱哈密顿连通图。

证明通过引理2 可得，则

3 总 结

通过研究文献[8]中关于二部图的弱哈密顿连通性的结论，联想到文献[7]中运用拓扑指数来讨论图的哈密顿性。由此受到启发，本文利用Wiener指数、Harary指数和hyper-Wiener指数分别给出了平衡二部图是弱哈密顿连通的充分条件。另外，二部图与泛圈图跟拓扑指数有着紧密的联系，这也是我今后的工作重点。