关于图中哈密尔顿圈存在的研究

Research on the Existence of Hamiltonian Cycles in Graphs

摘要: 每个顶点的度均为$r$ 的图被称为$r$ -正则图。本文首先证明了两个重要的结果：一是对于顶点数不超过$4r$ 的连通$r$ -正则二部图，它们是哈密尔顿图；二是对于顶点数不超过$5r-8$ 的连通$r$ -正则二部图，它们包含哈密尔顿路。Ng和Schultz在1997年提出了$k$ -序图和$k$ -序哈密尔顿图的概念，即对于图$G$ 的任意$k$ 阶顶点集$S$ (其中$k$ 是正整数)，如果$G$ 中存在一个圈按照$S$ 中顶点的给定顺序通过，则称$G$ 是$k$ -序图。特别地，如果这个圈是哈密尔顿圈，则称$G$ 是$k$ -序哈密尔顿图。本文证明了对于一个$k+1$ -连通且$k$ -序可圈的$n$ 阶图$G$ ，如果对于$V\left(G\right)$ 中每一对不相邻的顶点$x$ 和$y$ ，它们的度数之和$d_G\left(x\right)+d_G\left(y\right)$ 至少为$n$ ，则$G$ 是$k$ -序哈密尔顿图。

Abstract: A graph in which the degree of each vertex is $r$ is called an $r$ -regular graph. In this paper, two important results are first proved: Firstly, for a connected $r$ -regular bipartite graph with the number of vertices not exceeding $4r$ , it is a Hamiltonian graph; Secondly, for a connected $r$ -regular bipartite graph with the number of vertices not exceeding $5r-8$ , it contains a Hamiltonian path. In 1997, Ng and Schultz proposed the concepts of $k$ -ordered graphs and $k$ -ordered Hamiltonian graphs. That is, for any vertex set $S$ of order $k$ (where $k$ is a positive integer) in graph $G$ , if there exists a cycle in $G$ that passes through the vertices in $S$ according to the given order, then $G$ is called a $k$ -ordered graph. In particular, if this cycle is a Hamiltonian cycle, then $G$ is called a $k$ -ordered Hamiltonian graph. In this paper, it is proved that for a graph $G$ of order $n$ which is $\left(k+1\right)$ -connected and $k$ -ordered, if for every pair of non-adjacent vertices $x$ and $y$ in $V\left(G\right)$ , the sum of their degrees $d_G\left(x\right)+d_G\left(y\right)$ is at least $n$ , then $G$ is a $k$ -ordered Hamiltonian graph.

1. 引言

本文研究的所有图均为简单有限无向图，对于未在文中明确定义的符号和术语，我们参考了文献[1]。对于图$G$ ，它的顶点集用$V\left(G\right)$ 表示，边集用$E\left(G\right)$ 表示。图$G$ 的阶数，即顶点的数量用$G$ 表示。对于任意顶点$v\in V\left(G\right)$ 以及图$G$ 的任意一个顶点子集(或顶点子图) $H$ ，$N_H\left(v\right)$ 表示$v$ 在$H$ 中的邻点集，而$d_H\left(v\right)=\left|N_H\left(v\right)\right|$ 表示$v$ 在$H$ 中的度数。图$G$ 中顶点的最小度数和最大度数分别用$\delta \left(G\right)$ 和$\Delta \left(G\right)$ 表示。完全图，即每对不同的顶点之间都存在一条边的图，用$K_n$ 表示，其中$n$ 是图的阶数。完全二部图，即顶点可以被分成两个不相交的集合，且一个集合中的每个顶点都与另一个集合中的每个顶点相连，用$K_{n_1,n_2}$ 表示，其中$n_1$ 和$n_2$ 分别是两个部集的阶数。

一个包含图中所有顶点的圈被称为哈密尔顿圈。如果一个图包含哈密尔顿圈，那么这个图被称为哈密尔顿图。众所周知，判断一个图是否为哈密尔顿图是一个$NP$ -困难问题。因此，关于哈密尔顿图的充分条件得到了广泛的研究。其中最经典的定理是Dirac [2]在1952年证明的，即如果一个$n$ 阶图的最小度

数$\delta \left(G\right)\ge \frac{n}{2}$ ，那么这个图是哈密尔顿图。随后，Ore [3]给出了度数和条件下哈密尔顿圈存在的充分条件。

定理1.1 (Ore定理)：如果$n$ 阶图$G$ 满足对于任意一对不相邻的顶点$x$ 和$y$ ，都有$d_G\left(x\right)+d_G\left(y\right)\ge n$ ，那么$G$ 是哈密尔顿图。

正则图是指图中每个顶点的度数都相同的图。特别地，如果每个顶点的度均为$r$ ，则称其为$r$ -正则图。

关于2-连通正则图中哈密尔顿圈的存在性，Szekeres [4]首次探讨了在2-连通，$r$ -正则图$G$ 中，总点数$n$ 与正则度$r$ 之间的关系，以确定$G$ 是否为哈密尔顿图。Jackson [4]首次将hopping lemma运用于正则图的哈密尔顿性的研究，并证明了顶点数不超过$3r$ 的2-连通，$r$ -正则图是哈密尔顿图，且该结果中的界$3r$ 是最优的。排除一些特殊图类后，学者们进一步提高了这一上界，详见文献[5]-[7]。自然而然，在更高的连通度下，寻求更优的图总点数$n$ 的上界是有意义的。Häggkvist提出了一个猜想：对于正整数$m$ 和$r\ge 4$ ，顶点数不超过$\left(m+1\right)r$ 的$m$ -连通，$r$ -正则图是哈密尔顿图[8]。Jackson和Jung分别给出了构造，说明Häggkvist的猜想在$m\ge 4$ 时是错误的[9]。然而Jackson认为这个猜想在$m=3$ 时仍然成立。目前，对于点数较多的图，这一猜想在$m=3$ 时已经得到解决[10]，但对这一猜想的完整证明仍然是一个开放问题。随后，Cranston等人确定了连通$r$ -正则图中非哈密顿图的最小顶点数，他们证明了顶点数不超过$2r+2$ 的连通$r$ -正则图是哈密尔顿图，并构造了顶点数为$2r+3$ 和$2r+4$ 的连通$r$ -正则非哈密尔顿图[11]。

随着正则图哈密尔顿性问题的深入研究，Häggkvist在1976年提出了一个具有里程碑意义的猜想[8]：对于2-连通，$r$ -正则二部图，如果顶点数不超过$6r$ ，则该图是哈密尔顿图。这一猜想极大地推动了正则二部图哈密尔顿性问题的研究进程。李皓教授[9]通过构造一个具有$6r+2$ 个顶点的正则二部非哈密尔顿图，说明了Häggkvist猜想中的界$6r$ 是最优的。围绕这一猜想，Jackson在1994年取得了重大进展，他证明了对于顶点数不超过$6r-38$ 的2-连通$r$ -正则二部图，该图是哈密尔顿图，但这一猜想的完全解决仍需进一步的研究工作。

本文在连通正则二部图的哈密尔顿性问题的研究上提供了一个补充性的结果。

定理1.2：当$r\ge 8$ 时，顶点数不超过$4r$ 的连通$r$ -正则二部图是哈密尔顿图。

此外，作为定理1.2的推广，我们还证明了正则二部图中存在哈密尔顿路的一个充分条件。

定理1.3：当$r\ge 8$ 时，顶点数不超过$5r-8$ 的连通$r$ -正则二部图中存在哈密尔顿路。

对于图$G$ 的任意$k$ 阶顶点集$S$ ，其中$k$ 是正整数，并且给定$S$ 中顶点一个顺序，如果$G$ 中存在一个圈按照该给定顺序通过顶点集$S$ ，则称$G$ 为$k$ -序图。特别地，如果在$G$ 中存在一个哈密尔顿圈按照该给定顺序通过顶点集$S$ ，则称$G$ 为$k$ -序哈密尔顿图。这一概念最初由Ng和Schultz [12]在1997年提出的。显然，任意2-连通图都是2-序图，任意3-连通图都是3-序图。因此，对于$k\ge 4$ ，图的$k$ -序哈密尔顿性是一个有趣的研究领域。目前，关于图的$k$ -序性和$k$ -序哈密尔顿性的充分条件已有众多研究成果，包括度数和条件、广义度数和条件以及邻域条件等，具体内容可以参考综述文献[13]。在本文中，我们还证明了以下结果。

定理1.4：设$G$ 是一个$k+1$ -连通，$k$ -序$n$ 阶图，如果$G$ 满足对于任意一对不相邻的顶点$x$ 和$y$ 均有$d_G\left(x\right)+d_G\left(y\right)\ge n$ ，则$G$ 是$k$ -序哈密尔顿图。

2. 主要结论及其证明

2.1. 连通正则二部哈密尔顿图的充分条件

在后续的证明中，我们将依赖以下两个关键定理：

定理2.1 [14]：顶点数不超过$5r-8$ 的2-连通，$r$ -正则二部图是哈密尔顿图。

定理2.2 [15]：设$G$ 是一个顶点数不超过$3\Delta \left(G\right)-2$ 的2-连通图，则$G$ 中存在一个包含所有度为$\Delta \left(G\right)$ 的顶点的圈。

接下来，我们介绍一个门格定理的经典推论：

定理2.3 [16]：设$G$ 是一个$k$ -连通图，$x\in V\left(G\right)$ ，$S\subset V\left(G\right)-x$ ，并且$\left|S\right|\ge k$ ，则$G$ 中存在$k$ 条从$x$ 发向$S$ 的路，并且这$k$ 条路除了顶点$x$ 以外两两不相交。

在这一小节我们主要证明定理1.2和定理1.3。

定理1.2的证明：设$G$ 是一个顶点数不超过$4r$ 的连通$r$ -正则二部图。我们采用反证法，假设$G$ 不是哈密尔顿图。根据定理2.1，我们只需要证明$G$ 没有割点。假设$G$ 有一个割点$v$ ，则$G-v$ 至少有两个分支，记为$O_1$ 和$O_2$ 。对于$i\in \left\{1,2\right\}$ ，令$H_i=G\left[V\left(O_i\right)\cup \left\{v\right\}\right]$ 。因为$G$ 中所有顶点的度数均为$r$ ，并且除了$v$ ，$H_i$ 中的每个顶点的邻点都在$H_i$ 中，所以$H_i$ 至少有$2r$ 个顶点。如果$\left|H_i\right|=2r$ ，则$H_i=K_{r,r}$ ，因此$v$ 在某一个$H_i$ 中已经达到满度，这与$v$ 是割点矛盾。所以$G-v$ 的每个分支都有至少$2r$ 个顶点，那么$G$ 有至少$4r+1$ 个顶点，这与定理1.2的条件矛盾。

定理1.3的证明：设$G$ 是一个顶点数不超过$5r-8$ 的连通$r$ -正则二部图。如果$G$ 是2-连通图，根据定理2.1，$G$ 中存在一个哈密尔顿圈，结论证得。

因此，对于定理1.3的每个反例图，它都必须有一个割点。取一个反例图$G$ ，且$G$ 有一个割点$v$ 。如果$G-v$ 有至少三个分支，则根据定理1.2的证明，$G-v$ 的每个分支至少有$2r$ 个顶点，所以$G$ 至少有$6r+1$ 个顶点，这与$G$ 的顶点数不超过$5r-8$ 相矛盾。

因此，假设$G-v$ 只有两个分支，记为$O_1$ 和$O_2$ 。对于$i\in \left\{1,2\right\}$ ，令$H_i=G\left[V\left(O_i\right)\cup \left\{v\right\}\right]$ 。注意到除了$v$ 之外，$H_i$ 中的每个顶点的度均为$r$ 。如果$H_1$ 有一个割点$v_1$ ，则$G-\left\{v,v_1\right\}$ 的三个分支分别至少有$2r,2r-1,2r$ 个顶点，因此$G$ 至少有$2r+2r-1+2r+2=6r+1$ 个顶点，这与$G$ 的顶点数不超过$5r-8$ 相矛盾。所以$H_1$ 是2-连通的。同理，$H_2$ 也是2-连通的。因为$H_1$ 至少有$2r+1$ 个顶点，所以$2r+1\le \left|H_2\right|\le 3r-9$ ，同理，$2r+1\le \left|H_1\right|\le 3r-9$ 。因为每一个分支的点数不超过$3r-9$ ，满足定理2.2的条件。所以根据定理2.2，对于$i\in \left\{1,2\right\}$ ，$H_i$ 有一个包含除顶点$v$ 以外所有顶点的圈，因此$H_i$ 有一个以$v$ 为端点的哈密尔顿路。所以$G$ 中存在一条哈密尔顿路。

2.2. k-序哈密尔顿圈的充分条件

在这一小节我们主要证明定理1.4。

定理1.4的证明：设$G$ 是一个$k+1$ -连通，$k$ -序$n$ 阶图。令$S=\left\{c_1,c_2,\cdots ,c_k\right\}$ 是$G$ 中一个有序的顶点集。根据$G$ 是$k$ -序图的假设条件，存在一个圈$C$ 在$G$ 中按照给定顺序通过$S$ ，并且使得$C$ 的阶数尽可能的大。如果$C$ 是哈密尔顿圈，则证明完毕。假设$C$ 不是哈密尔顿圈，令$G-C=H$ 且$\left|H\right|=h$ 。集合$S$ 将$C$ 分为$k$ 个片段$\left[c_{1}C{c}_2\right]$ ，$\left[c_{2}C{c}_3\right]$ ，…，$\left[c_{k-1}C{c}_k\right]$ ，$\left[c_{k}C{c}_1\right]$ 。

引理2.4：如果$h\ge 3$ ，则$H$ 是哈密尔顿图；否则$H$ 是完全图。

当$h=1$ 或$h=2$ 时，显然$H$ 是完全图。当$h\ge 3$ 时，注意$H$ 中任意一个的顶点在$C$ 上的总邻点数不超

过$\frac{\left|C\right|}{2}$ ，否则与$C$ 的最大性矛盾。由此可以推出对于$H$ 中任意一对不相邻的顶点$x$ 和$y$ 均有 $d_C\left(x\right)+d_C\left(y\right)\le \left|C\right|$ ，因此$d_H\left(x\right)+d_H\left(y\right)\ge n-\left|C\right|=\left|H\right|$ 。根据定理1.1可知$H$ 是哈密尔顿图。

引理2.5：在每个片段$\left[c_{i}C{c}_{i+1}\right],i=1,2,\cdots ,k$ ，$c_{k+1}=c_1$ 上最多只有一个顶点是$H$ 的邻点。

采用反证法，假设在$\left[c_{i}C{c}_{i+1}\right]$ 上存在不同的顶点$x,y$ 分别与$u,v\in H$ 相连，并且满足在$xCy$ 上$H$ 没有其他邻点。设$ux,vy\in E\left(G\right)$ 。注意到我们允许$u=v$ 。令$\left|\left(xCy\right)\right|=s$ 。因为$u$ 不可插入到$C$ ，我们得到

$d\left(u\right)\le h-1+\frac{n-h-s+1}{2}$ 。如果我们可以依次将$\left(xCy\right)$ 中的顶点插入到$\left[yCx\right]$ 上，则我们可以将$C$ 扩大为一个包含$u$ 和$V\left(C\right)$ 的圈$C^{\prime }$ ，并且$C^{\prime }$ 按照给定顺序通过$S$ ，这与$C$ 的最大性矛盾。因此，在$\left(xCy\right)$ 上存在一个顶点$w$ 不可插入到$\left[yCx\right]$ 上。由此推出$d\left(w\right)\le s-1+\frac{n-h-s+1}{2}$ ，所以$d\left(u\right)+d\left(w\right)\le n-1$ ，矛盾。

根据引理2.5，我们可以推出$\left|N_C\left(H\right)\right|\le k$ 。因为$G$ 是$k+1$ -连通图，当$\left|C\right|\ge k+1$ 时，根据定理2.3，我们得到$\left|N_C\left(H\right)\right|\ge k+1$ ，矛盾。当$\left|C\right|=k$ 时，我们推出$C$ 上的每一个顶点都与$H$ 相连，显然可以找到一个更长的圈按顺序通过$S$ ，这与$C$ 的最大性矛盾。

3. 总结及展望

本文首先探讨了连通r-正则二部图中哈密尔顿圈和哈密尔顿路的存在性，这对已有研究进行了补充。另外，在正则二部图的哈密尔顿圈问题研究领域，尚存很多悬而未决的猜想。特别地，关于在2-连通条件下正则二部图的哈密尔顿圈存在的猜想，至今仍未得到完全解决。此外，随着连通度的提高，如下问题也是可以继续考虑的一个方向。

问题3.1：顶点数不超过8k-正则二部图是哈密尔顿图。

此外，本文还探讨了过特殊元素的哈密尔顿圈存在的子方向，即k-序哈密尔顿圈的存在性问题。这一研究课题在近几年得到了学者们的广泛研究。本文的结论表明，在$k+1$ -连通，k-序图中，经典的Ore条件可以保证k-序哈密尔顿圈的存在。

基金项目

山西省重大研究项目(202202020101006)。

NOTES

^*通讯作者。