Hamilton cycles, minimum degree, and bipartite holes

Journal article

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erdős. In detail, an inline image-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with inline image and inline image such that there are no edges between S and T; and inline image is the maximum integer r such that G contains an inline image-bipartite-hole for every pair of nonnegative integers s and t with inline image. Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least inline image. From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge-disjoint Hamilton cycles. We see that for dense random graphs inline image, the probability of failing to contain many edge-disjoint Hamilton cycles is inline image. Finally, we discuss the complexity of calculating and approximating inline image.

Authors: McDiarmid, C; Yolov, N

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Journal of Graph Theory
• Volume: 86
• Issue: 3
• Pages: 277–285
• Publication date: 2017-07-07
• Acceptance date: 2016-11-09
• DOI: 10.1002/jgt.22114
• EISSN: 1097-0118
• ISSN: 0364-9024
• Keywords: extremal graph theory; bipartite hole; hamilton cycle; random graphs