Wiener指数与图的hamiltonian性研究

曾 婷

（湖南城市学院，湖南 益阳 413000）

设G是简单连通图，顶点集和边集分别为V(G)、E(G).在图 G 中，dG(v)表示顶点 v 的度，dG(u,v)表示G中两顶点u和v的距离，即为u,v之间最短路的长度.

图G的Wiener指数[2,4,8]，记作W(G),由美国化学家Harold Wiener于1947年提出，定义为W(G)=

一个连通图中若含有一条Hamilton路，即通过图中所有顶点的路，则它被称为可迹图.若有一个通过所有顶点的Hamilton圈，则称为Hamilton图.关于Hamilton图的存在性，已有许多充分条件，如Dirac条件，Ore条件，Fan条件等等.近来，Hua和Wang 利用哈拉里指数，给出了连通图变成可迹图的充分条件.本文将为连通二部图成为特殊的二部图即Hamilton图建立一个新的充分条件.同时得出所有哈密尔顿图的最大和最小的Wiener指数.

为完成此结论，还需要以下术语.图G中顶点v的偏心距[5-7]定义为 ecG(v)=max{dG(u,v)|u∈V(G)}.分别将含n个顶点的完全图、路及圈表示为Kn,Pn,Cn.令Kn,n-1为一个完全二部图，其中二部集为X，Y，且|X|=n，|Y|=n-1.令为含2n个顶点的二部图，它是由Kn,n-1图的X顶点集中的一个顶点与另一个孤立点之间添加一条悬挂边而得来的.为简单起见，下文中分别用di，代替dG(vi)和(vi).其他相关标记和术语可参考著作[1].

1 基本引理

推出主要结论之前，先引入一个结果，即给出二部连通图Hamilton化的一个充分条件.

引理[1]G:=G[X,Y]是顶点数为|X|=|Y|=n≥2，且度序列为(d1,d2,…,d2n)的连通二部图，这里d1≤d2≤…≤d2n.若不存在小于或等于的整数k，使得dk≤k 和 dn≤n-k，则 G 是 Hamilton 图.

2 主要结论

下面以Wiener指数的形式，给出一个连通二部图Hamilton化的新的充分条件.

命题2.1令G:=G{X,Y]是顶点为|X|=|Y|=n≥2的连通二部图，若

则G是Hamilton图.

证明假设G不是Hamilton图，而是一个连通二部图，其度序列为(d1,d2,…,d2n)，且 d1≤d2≤…≤d2n.由引理1.1可知，存在一个，使得 dk≤k和dn≤n-k.可以求得，对G中任意的i(i=1,2,…,2n)，有D^i≥di+2(2n-1-di).由（1）式，得到

结合这一结论及上述假设，易知W(G)=3n2-n-1.因此，（2）（3）（4）式中所有不等式应变为等式.

由此可知，

(a)由（2）式的等式知，图G的直径不超过2.

(b)由（3）式的等式，有 d1=d2=…=dk=k，dk+1=…=dn=n-k及dn+1=…=d2n=n.

(c)由（4）式的等式，有 k=1 或 k=n-1.

因此，可设 k≠n-1，由（c），有 k=1.再根据（b），可推得.但是G中这个唯一的悬挂顶点偏心距为 3，也与（a）矛盾.

综上，G是Hamilton图.证毕.

以上通过Wiener指数获得了Hamilton图的一个新的充分条件，只要图的Wiener指数不超过上界而给定一个值，即可推出这个图是Hamilton图.那么在所有Hamilton图中，哪些图可达到最大或最小Wiener指标？不难知道，从一个图中移走一条边，会增加其Wiener指数，又因为此图为Hamilton图（即含有Hamilton圈），所以我们得到以下结论：

命题2.2 所有顶点为n的Hamilton图中，圈Cn和完全图Kn分别达到最大和最小Wiener指数.

3 结语

从文中看出，只要满足关于Wiener指数的一定的不等式，就能知道一个连通二部图能否含有Hamilton圈，这为研究图的Hamiltonian性提供了方便.最后还得到了所有Hamilton图的最大最小Wiener指数.