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

Daniela Kühn, Allan Lo, Deryk Osthus, Katherine Staden

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
163 Downloads (Pure)

Abstract

We prove that, for large n, every 3-connected D-regular graph on n vertices with $D \geq n/4$ is Hamiltonian. This is best possible and confirms a conjecture posed independently by Bollob\'as and H\"aggkvist in the 1970s. The proof builds on a structural decomposition result proved recently by the same authors.
Original languageEnglish
Pages (from-to)85-145
Number of pages61
JournalJournal of Combinatorial Theory. Series B
Volume121
Early online date31 Dec 2015
DOIs
Publication statusPublished - 1 Nov 2016

Keywords

  • Hamilton cycles
  • Connectivity
  • robust expansion
  • regular graphs

Fingerprint

Dive into the research topics of 'Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs'. Together they form a unique fingerprint.

Cite this