Hamilton cycles, minimum degree, and bipartite holes

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.