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

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

We prove that, for large n, every 3-connected D-regular graph on n vertices with is Hamiltonian. This is best possible and verifies the only remaining case of a conjecture posed independently by Bollobás and Häggkvist in the 1970s. The proof builds on a structural decomposition result proved recent...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Kühn, D, Lo, A, Osthus, D, Staden, K
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	Elsevier 2015

Eitemau Tebyg

An exact minimum degree condition for Hamilton cycles in oriented graphs
gan: Keevash, P, et al.
Cyhoeddwyd: (2008)

Matchings and Hamilton cycles in hypergraphs
gan: Daniela Kühn, et al.
Cyhoeddwyd: (2005-01-01)

A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
gan: Sah, Ashwin, et al.
Cyhoeddwyd: (2021)

A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
gan: Sah, Ashwin, et al.
Cyhoeddwyd: (2021)

On the Bishop-Phelps-Bollobás Property for Numerical Radius
gan: Sun Kwang Kim, et al.
Cyhoeddwyd: (2014-01-01)

Combinatorics in the exterior algebra and the Bollobás Two Families Theorem
gan: Scott, A, et al.
Cyhoeddwyd: (2021)

On degree sequences forcing the square of a Hamilton cycle
gan: Staden, K, et al.
Cyhoeddwyd: (2017)

Bishop-Phelps-Bollobás property for positive operators when the domain is L∞
gan: María D. Acosta, et al.
Cyhoeddwyd: (2021-08-01)

Finding Hamilton cycles in random intersection graphs
gan: Katarzyna Rybarczyk
Cyhoeddwyd: (2018-03-01)

Edge Disjoint Hamilton Cycles in Knödel Graphs
gan: Palanivel Subramania Nadar Paulraja, et al.
Cyhoeddwyd: (2016-07-01)

Hamilton Cycles in Double Generalized Petersen Graphs
gan: Sakamoto Yutaro
Cyhoeddwyd: (2019-02-01)

Hamilton cycles in almost distance-hereditary graphs
gan: Chen Bing, et al.
Cyhoeddwyd: (2016-01-01)

Discontinuous solutions for Hamilton-Jacobi equations: Uniqueness and regularity
gan: Chen, G, et al.
Cyhoeddwyd: (2003)

Packing, counting and covering Hamilton cycles in random directed graphs
gan: Ferber, A, et al.
Cyhoeddwyd: (2017)

A Note Concerning Hamilton Cycles in Some Classes of Grid Graphs
gan: A. N.M. Salman, et al.
Cyhoeddwyd: (2013-12-01)

$K_{\ell}^{-}$-factors in graphs
gan: Daniela Kühn, et al.
Cyhoeddwyd: (2005-01-01)

A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs
gan: Tang Long, et al.
Cyhoeddwyd: (2020-02-01)

Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications
gan: Suliman Khan, et al.
Cyhoeddwyd: (2021-02-01)

Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
gan: Wu Jichang, et al.
Cyhoeddwyd: (2021-05-01)

Energy Conditions for Hamiltonicity of Graphs
gan: Guidong Yu, et al.
Cyhoeddwyd: (2014-01-01)

Hamilton-Connected Mycielski Graphs∗
gan: Yuanyuan Shen, et al.
Cyhoeddwyd: (2021-01-01)

Spectral Radius and Hamiltonicity of Graphs
gan: Yu Guidong, et al.
Cyhoeddwyd: (2019-11-01)

The matching number and Hamiltonicity of graphs
gan: Rao Li
Cyhoeddwyd: (2020-09-01)

graph, Hamiltonian path, Hamiltonian cycle, Hamilton-connected graph, detour index, NP-complete problems, Platonic solids, convex polytopes
gan: Abdelgader Siddig, et al.
Cyhoeddwyd: (2021-02-01)

Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
gan: Mou, G, et al.
Cyhoeddwyd: (2016)

Counting Hamilton decompositions of oriented graphs
gan: Ferber, A, et al.
Cyhoeddwyd: (2017)

On hamiltonicity of uniform random intersection graphs
gan: Mindaugas Bloznelis, et al.
Cyhoeddwyd: (2010-12-01)

Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
gan: Mou, Gao, et al.
Cyhoeddwyd: (2017)

Signless Laplacian Spectral Conditions for Hamiltonicity of Graphs
gan: Guidong Yu, et al.
Cyhoeddwyd: (2014-01-01)

Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
gan: Zheng Wei, et al.
Cyhoeddwyd: (2022-02-01)

Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
gan: Li Binlong, et al.
Cyhoeddwyd: (2016-11-01)

Hamiltonicity and Generalised Total Colourings of Planar Graphs
gan: Borowiecki Mieczysław, et al.
Cyhoeddwyd: (2016-05-01)

On hamiltonicity of 1-tough triangle-free graphs
gan: Wei Zheng, et al.
Cyhoeddwyd: (2021-10-01)

Some sufficient conditions on hamilton graphs with toughness
gan: Gaixiang Cai, et al.
Cyhoeddwyd: (2022-10-01)

Edge condition for hamiltonicity in balanced tripartite graphs
gan: Janusz Adamus
Cyhoeddwyd: (2009-01-01)

The regularity method for graphs with few 4‐cycles
gan: Conlon, David, et al.
Cyhoeddwyd: (2022)

Identifying Hamilton cycles in the Cartesian product of directed cycles
gan: Zbigniew R. Bogdanowicz
Cyhoeddwyd: (2020-01-01)

Connectivity and Hamiltonicity of Canonical Colouring Graphs of Bipartite and Complete Multipartite Graphs
gan: Ruth Haas, et al.
Cyhoeddwyd: (2018-03-01)

Symmetric Hamilton Cycle Decompositions of Complete Multigraphs
gan: Chitra V., et al.
Cyhoeddwyd: (2013-09-01)

Regular graphs with a cycle as a star complement
gan: Zoran Stanić
Cyhoeddwyd: (2024-11-01)