利用Wiener指数、hyper-Wiener指数及Harary指数给出泛圈图的充分条件

胡启明， 许 欢， 叶 铭

(合肥幼儿师范高等专科学校 公共教学部，安徽 合肥 230013)

引 言

设G(V,E)是n阶简单连通图，顶点用vi(1in)表示，顶点集{v1,v2,…,vn}用V(G)(或V)表示；边集用E(G)(或E)表示，其元素可简记作vivj(1i,jn)，称为边[1]。称顶点vi(或vj)与边vivj是关联的，称边vivj的两个端点vi和vj是相邻的。若图G中的任意一个顶点vi(1in)与其他顶点都相邻，则称G为完全图，记作Kn。用或(G)c)表示图G的补图，其中是由G中所有不相邻的两个顶点连成的边组成的集合。图G中与vi关联的边数称为顶点vi的度，用dG(vi)表示，图G的最小度记为δ(G)。图G中顶点vi和vj之间所有路的最小长度称为vi与vj之间的距离，记作dG(vi,vj)。

若对于任意的正整数k(3k

用G1∪G2表示G1和G2的并图，其中V(G1∪G2)=V(G1)∪V(G2)，E(G1∪G2)=E(G1)∪E(G2)；如果G1和G2没有公共顶点，G1和G2的并图记为G1+G2；若G1=G2=…=Gk，则G1∪G2∪…∪Gk记为kG1。

用G1∨G2表示G1和G2的联图，其等于((G1)c∪(G2)c)c，即V(G1∨G2)=V(G1)∪V(G2)，E(G1∨G2)为G1的边、G2的边和由G1中每个顶点与G2中每个顶点连成的边组成的集合。

图G的Wiener指数[2]记作W(G)，是指G中任意两个顶点vi和vj的距离之和，即

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

图G的Harary指数[5]记作H(G)，是指G中任意两个顶点vi和vj的距离倒数之和，即

对于任意给定的无向图G，怎样判断它是否包含一个哈密尔顿圈？这就是举世闻名的NP完全问题。因为图的拓扑指数能很好的反映图的结构性质且便于计算，近年来人们试图利用图的拓扑指数来刻画图的哈密尔顿性，如2013年华洪波等人[6]首次用Harary指数给出了连通图有哈密尔顿路的一个充分条件。随后曾婷[7]利用Harary指数给出平衡二部图有哈密尔顿圈的一个充分条件。杨立辉[8]给出了连通图存在哈密尔顿路的关于Wiener指数的一个充分条件。Rao Li[9,10]分别给出了连通图是哈密尔顿图和哈密尔顿连通图的关于Harary指数和Wiener指数的充分条件。刘瑞芳[11,12]延伸了[7,8]中的结果。华洪波等人[13]给出了给定最小度的连通图、平衡二部图可迹性与哈密尔顿性的关于Harary指数和Wiener指数的充分条件。基于前面的研究基础，冯立华等人在[14]中又给出了k-哈密尔顿，k-路覆盖，k-边哈密尔顿的关于Harary指数和Wiener指数的充分条件。特别是最近舒阿秀等[15]研究了泛圈图的拓扑指数条件，利用图及其补图的Wiener指数、hyper-Wiener指数，给出了具有最小度条件的简单连通图是泛圈图的充分条件；余桂东等[16]给出了泛圈图的新的边数条件，以及谱半径和无符号Laplacian谱半径条件。受文献[15,16]的启发，本文利用文献[16]中泛圈图的新的边数条件，利用图及其补图的Wiener指数、hyper-Wiener指数，Harary指数给出了具有最小度条件的简单连通图是泛圈图的充分条件，其中Wiener指数、hyper-Wiener指数的充分条件优化了文献[15]中的结论。

1 相关引理

记NP1={K2∨(Kn-4+2K1),K5∨6K1,K3∨(K2+3K1),K3∨(K1+K1，4),K3∨(K2+K1，3),(K2∨2K1∨5K1,K4∨5K1,K1，2∨4K1,K2∨(K1+K1，3),K3∨4K1}。

记NPC={K4∨5K1,K2∨(K3+2K1),K3∨4K1,K1，2∨4K1,K2∨(K1+K1，3),K2∨(K2+2K1),K1∨2K2,K2∨3K1}。

2 主要结论

定理2.1设简单连通图G的顶点数为n(n≥5)，δ(G)≥2。若

W(G)

则G要么是一个泛圈图，要么是一个二部图，要么属于NP1。

于是有

=n(n-1)-m

这与条件W(G)矛盾。

下面讨论G∈NP1的情况：

综上，当G∈NP1时，有W(G)

故G是一个泛圈图，或是一个二部图，或属于NP1。

推论2.2设G为n(n≥9)阶简单连通图，δ≥2，如果

W(G)

则G是一个泛圈图，除非G是一个二部图或G∈{K4∨5K1，K3∨4K1}。

定理2.3[15]设G为n阶简单连通图，δ≥2，如果

W(G)

则G是一个泛圈图，除非G是一个二部图或G∈NPC。

注：由于{K4∨5K1，K3∨4K1}⊂NPC，故n≥9时，定理2.1推广了定理2.3。

则G要么是泛圈图，要么是一个二部图。

于是有

则G是一个泛圈图，除非G是一个二部图。

定理2.6设简单连通图G的顶点数为n(n≥5)，δ(G)≥2。若

WW(G)

则G要么是一个泛圈图，要么是一个二部图，要么属于NP1。

于是有

这与所给条件WW(G)矛盾。

下面讨论G∈NP1的情况：

综上，当G∈NP1时，有WW(G)

故G是一个泛圈图，或是一个二部图，或G∈NP1。

推论2.7设G为n(n≥9)阶简单连通图，δ≥2，如果

WW(G)

则G是一个泛圈图，除非G是一个二部图或G∈{K4∨5K1，K3∨4K1}。

定理2.8[15]设G为n阶简单连通图，δ≥2，如果

WW(G)

则G是一个泛圈图，除非G是一个二部图或G∈NPC。

注：由于{K4∨5K1，K3∨4K1}⊂NPC，故n≥9时，定理2.6推广了定理2.8。

则G要么是一个泛圈图，要么是一个二部图。

于是有

则G是一个泛圈图，除非G是一个二部图。

定理2.11设简单连通图G的顶点数为n(n≥5)，δ(G)≥2。若

则G要么是一个泛圈图，要么是一个二部图，要么属于NP1。

于是有

下面讨论G∈NP1的情况：

故假设不成立，则G是一个泛圈图，或是一个二部图，或G∈NP1。

则G要么是泛圈图，要么是一个二部图。

于是有