On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
From MaRDI portal
Publication:3225113
DOI10.1137/110821299zbMath1237.05187arXiv1101.3099OpenAlexW3100625388WikidataQ105584131 ScholiaQ105584131MaRDI QIDQ3225113
Michael Krivelevich, Sonny Ben-Shimon, Benjamin Sudakov
Publication date: 15 March 2012
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.3099
Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items (31)
Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Dirac's theorem for random graphs ⋮ On the Hamiltonicity of random bipartite graphs ⋮ Hitting time results for Maker-Breaker games ⋮ Generating random graphs in biased Maker-Breaker games ⋮ Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ Robust Hamiltonicity of random directed graphs ⋮ Spanning Trees at the Connectivity Threshold ⋮ Graph Tilings in Incompatibility Systems ⋮ Perfect matchings in random subgraphs of regular bipartite graphs ⋮ The global resilience of Hamiltonicity in \(G(n, p)\) ⋮ Packing arborescences in random digraphs ⋮ The Pizza-Cutter’s Problem and Hamiltonian Paths ⋮ The Threshold Probability for Long Cycles ⋮ Hamilton decompositions of regular expanders: applications ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Packing Arborescences in Random Digraphs ⋮ Optimal covers with Hamilton cycles in random graphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ On covering expander graphs by hamilton cycles ⋮ Robust Hamiltonicity of Dirac graphs ⋮ Virtually fibering random right-angled Coxeter groups -- extended abstract ⋮ Random directed graphs are robustly Hamiltonian ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs ⋮ Note on matching preclusion number of random graphs ⋮ Edge-disjoint Hamilton cycles in random graphs ⋮ Hamiltonicity in random graphs is born resilient
This page was built for publication: On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
