Dirac’s theorem for random regular graphs

DOI10.1017/S0963548320000346zbMath1466.05195arXiv1903.05052OpenAlexW3081824977MaRDI QIDQ4993119

Daniela Kühn, Alberto Espuny Díaz, Deryk Osthus, António Girão, Padraig Condon

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclerandom regular graphDirac's theoremlocal resilience

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Related Items

Hamiltonicity of graphs perturbed by a random regular graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On two Hamilton cycle problems in random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The spectral gap of dense random regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• Sandwiching random graphs: universality between random graph models
• Hamiltonicity in random graphs is born resilient
• Robust Hamiltonicity of random directed graphs
• Weighted sums of certain dependent random variables
• Random regular graphs of high degree
• Random directed graphs are robustly Hamiltonian
• Corrádi and Hajnal's Theorem for Sparse Random Graphs
• Local resilience of almost spanning trees in random graphs
• Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Pattern Colored Hamilton Cycles in Random Graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Dirac's theorem for random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Uniform generation of random regular graphs of moderate degree
• Local resilience of graphs
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Local resilience of an almost spanning k‐cycle in random graphs
• The Bandwidth Theorem in sparse graphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Long paths and Hamiltonicity in random graphs