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( G ) 中每一对不相邻的顶点 x 和 y ，它们的度数之和 d G ( x )+ d G ( y ) 至少为 n ，则 G 是 k -序哈密尔顿图。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 ( k+1 ) -connected and k -ordered, if for every pair of non-adjacent vertices x and y in V( G ) , the sum of their degrees d G ( x )+ d G ( y ) is at least n , then G is a k -ordered Hamiltonian graph.