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

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.