On one extension of Dirac's theorem on Hamiltonicity

Abstract

The classical Dirac theorem asserts that every graph G on n >= 3 vertices with minimum degree delta(G) >= [n/2] is Hamiltonian. The lower bound of [n/2] on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where delta(G) >= [n/2] by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph G with delta(G) >= [n/2], or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when delta(G) >= [n/2] and is promising for extending the results of this paper to the cases with smaller degree bounds. (C) 2017 Elsevier B.V. All rights reserved.