The robust component structure of dense regular graphs and applications

DOI10.1112/PLMS/PDU039zbMATH Open1307.05130arXiv1401.0424OpenAlexW3101429032MaRDI QIDQ2940076FDOQ2940076

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

Publication date: 26 January 2015

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

Abstract: In this paper, we study the large-scale structure of dense regular graphs. This involves the notion of robust expansion, a recent concept which has already been used successfully to settle several longstanding problems. Roughly speaking, a graph is robustly expanding if it still expands after the deletion of a small fraction of its vertices and edges. Our main result allows us to harness the useful consequences of robust expansion even if the graph itself is not a robust expander. It states that every dense regular graph can be partitioned into `robust components', each of which is a robust expander or a bipartite robust expander. We apply our result to obtain (amongst others) the following. (i) We prove that whenever $eps>0$, every sufficiently large 3-connected D-regular graph on n vertices with $Dgeq(1/4+eps)n$ is Hamiltonian. This asymptotically confirms the only remaining case of a conjecture raised independently by Bollob'as and H"aggkvist in the 1970s. (ii) We prove an asymptotically best possible result on the circumference of dense regular graphs of given connectivity. The 2-connected case of this was conjectured by Bondy and proved by Wei.

Full work available at URL: https://arxiv.org/abs/1401.0424

Recommendations

• The robust component structure of dense regular graphs
• Approximate Hamilton decompositions of robustly expanding regular digraphs
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Hamilton cycles in regular 3-connected graphs
• Hamilton decompositions of regular expanders: applications

zbMATH Keywords

Hamiltonicityrobust expansiondense regular graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Density (toughness, etc.) (05C42)

Cites Work

• Longest cycles in regular graphs
• Dominating cycles in regular 3-connected graphs
• Hamilton cycles in regular 3-connected graphs
• Hamilton cycles in regular 2-connected graphs
• A survey on Hamilton cycles in directed graphs
• Title not available (Why is that?)
• Hamiltonian degree sequences in digraphs
• A proof of Sumner's universal tournament conjecture for large tournaments
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Hamilton cycles in 2-connected regular bipartite graphs
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• Title not available (Why is that?)
• An approximate version of Sumner's universal tournament conjecture
• Long paths and cycles in oriented graphs
• Hamilton cycles in dense vertex-transitive graphs
• On the circumferences of regular 2-connected graphs
• A sharp refinement of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences
• A note on regular Ramsey graphs

Cited In (13)

• Path decompositions of tournaments
• Cycle partitions of regular graphs
• Hamilton cycles in dense regular digraphs and oriented graphs
• Random perfect matchings in regular graphs
• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• Perfect matchings in random subgraphs of regular bipartite graphs
• The robustness of LWPP and WPP, with an application to graph reconstruction
• The robust component structure of dense regular graphs
• Hamilton cycles in sparse robustly expanding digraphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• A note on Hamilton decompositions of even-regular multigraphs
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: The robust component structure of dense regular graphs and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940076)