The robust component structure of dense regular graphs and applications
From MaRDI portal
Publication:2940076
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 , every sufficiently large 3-connected D-regular graph on n vertices with 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.
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
Cites work
- scientific article; zbMATH DE number 3630799 (Why is no real title available?)
- scientific article; zbMATH DE number 908781 (Why is no real title available?)
- A note on regular Ramsey graphs
- A proof of Sumner's universal tournament conjecture for large tournaments
- A sharp refinement of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences
- A survey on Hamilton cycles in directed graphs
- An approximate version of Sumner's universal tournament conjecture
- Dominating cycles in regular 3-connected graphs
- Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
- Hamilton cycles in 2-connected regular bipartite graphs
- Hamilton cycles in dense vertex-transitive graphs
- Hamilton cycles in regular 2-connected graphs
- Hamilton cycles in regular 3-connected graphs
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Hamilton decompositions of regular expanders: applications
- Hamiltonian degree sequences in digraphs
- Long paths and cycles in oriented graphs
- Longest cycles in regular graphs
- On the circumferences of regular 2-connected 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)
