On two Hamilton cycle problems in random graphs

DOI10.1007/s11856-008-1028-8zbMath1145.05049OpenAlexW2016267660WikidataQ57401483 ScholiaQ57401483MaRDI QIDQ948883

Michael Krivelevich, Alan M. Frieze

Publication date: 16 October 2008

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11856-008-1028-8

zbMATH Keywords

random graphnumber of edge disjoint Hamilton cyclesremoving edges without destroying Hamiltonicity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (35)

Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ Packing tight Hamilton cycles in 3-uniform hypergraphs ⋮ 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 ⋮ Pancyclic subgraphs of random graphs ⋮ 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 ⋮ Packing tree factors in random and pseudo-random graphs ⋮ Conflict-free connection number of random graphs ⋮ Proper connection number of random graphs ⋮ Hamilton decompositions of regular expanders: applications ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ Packing and counting arbitrary Hamilton cycles in random digraphs ⋮ 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 ⋮ Hamiltonicity thresholds in Achlioptas processes ⋮ Local resilience of almost spanning trees in random graphs ⋮ Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs ⋮ Random directed graphs are robustly Hamiltonian ⋮ Bandwidth theorem for random graphs ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs ⋮ Note on matching preclusion number of random graphs ⋮ Approximate Hamilton decompositions of random graphs ⋮ Edge-disjoint Hamilton cycles in random graphs ⋮ Hamiltonicity in random graphs is born resilient ⋮ Biased games on random boards ⋮ Waiter-client and client-waiter Hamiltonicity games on random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Hamiltonian circuits in random graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the existence of Hamiltonian cycles in a class of random graphs
• Local resilience of graphs
• How many random edges make a dense graph hamiltonian?

This page was built for publication: On two Hamilton cycle problems in random graphs