Hamilton cycles, minimum degree and bipartite holes

Abstract

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 $(s,t)$-bipartite-hole in a graph $G$ consists of two disjoint sets of vertices $S$ and $T$ with $|S|=s$ and $|T|=t$ such that there are no edges between $S$ and $T$; and $\tilde{\alpha }(G)$ is the maximum integer $r$ such that $G$ contains an $(s,t)$-bipartite-hole for every pair of non-negative integers $s$ and $t$ with $s+t=r$. Our central theorem is that a graph $G$ with at least $3$ vertices is Hamiltonian if its minimum degree is at least $\tilde{\alpha }(G)$. 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 $G(n,p)$, the probability of failing to contain many edge-disjoint Hamilton cycles is $(1-p{)}^{(1+o(1))n}$. Finally, we discuss the complexity of calculating and approximating $\tilde{\alpha }(G)$.