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

doi:10.1016/j.jctb.2015.12.003

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

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

251 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 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	https://doi.org/10.1016/j.jctb.2015.12.003
Publication status	Published - 1 Nov 2016

Keywords

Hamilton cycles
Connectivity
robust expansion
regular graphs

Access to Document

10.1016/j.jctb.2015.12.003

Kuhn_et_al_Solution_problem_Bollobas_Haggkvist_Journal_Combinatorial_Theory_Post-Print
Checked Feb 2016
Accepted author manuscript, 664 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs
Kuhn, D. (Principal Investigator)
European Commission, European Commission - Management Costs
1/12/10 → 30/11/15
Project: Research

Cite this

@article{6a4bb0a06d8643edb7ec1370dce1e0d0,

title = "Solution to a problem of Bollob{\'a}s and H{\"a}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 \textbackslash{}geq n/4\$ is Hamiltonian. This is best possible and confirms a conjecture posed independently by Bollob\textbackslash{}'as and H\textbackslash{}{"}aggkvist in the 1970s. The proof builds on a structural decomposition result proved recently by the same authors.",

keywords = "Hamilton cycles, Connectivity, robust expansion, regular graphs",

author = "Daniela K{\"u}hn and Allan Lo and Deryk Osthus and Katherine Staden",

year = "2016",

month = nov,

day = "1",

doi = "10.1016/j.jctb.2015.12.003",

language = "English",

volume = "121",

pages = "85--145",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Kühn, Daniela

AU - Lo, Allan

AU - Osthus, Deryk

AU - Staden, Katherine

PY - 2016/11/1

Y1 - 2016/11/1

N2 - 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.

AB - 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.

KW - Hamilton cycles

KW - Connectivity

KW - robust expansion

KW - regular graphs

U2 - 10.1016/j.jctb.2015.12.003

DO - 10.1016/j.jctb.2015.12.003

M3 - Article

SN - 0095-8956

VL - 121

SP - 85

EP - 145

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Projects

FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs

Cite this