Projects per year
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 language | English |
---|---|
Pages (from-to) | 85-145 |
Number of pages | 61 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 121 |
Early online date | 31 Dec 2015 |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs
European Commission, European Commission - Management Costs
1/12/10 → 30/11/15
Project: Research