Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs

Abstract

We prove that, for large $n$, every $3$-connected $D$-regular graph on $n$ vertices with $D\ge n/4$ is Hamiltonian. This is best possible and confirms a conjecture posed independently by Bollobás and Häggkvist in the 1970s. The proof builds on a structural decomposition result proved recently by the same authors.

42 pages, to appear in JCTB

Cited by in corpus (1)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective