On two Hamilton cycle problems in random graphs

DOI10.1007/S11856-008-1028-8zbMATH Open1145.05049OpenAlexW2016267660WikidataQ57401483 ScholiaQ57401483MaRDI QIDQ948883FDOQ948883

Authors: Michael Krivelevich, Alan 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

Recommendations

• On the number of hamilton cycles in a random graph
• scientific article; zbMATH DE number 4087714
• Publication:4729826
• scientific article; zbMATH DE number 3950585
• Hamiltonian cycles in random regular graphs
• scientific article; zbMATH DE number 17675
• On the Number of Hamilton Cycles in Sparse Random Graphs
• scientific article; zbMATH DE number 1496581
• Hamilton cycles in random graphs with a fixed degree sequence

zbMATH Keywords

random graphnumber of edge disjoint Hamilton cyclesremoving edges without destroying Hamiltonicity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (50)

• Random directed graphs are robustly Hamiltonian
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• Hamiltonicity of random graphs in the stochastic block model
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Local resilience of almost spanning trees in random graphs
• Dirac-type theorems in random hypergraphs
• Hamilton decompositions of regular expanders: applications
• On prisms, Möbius ladders and the cycle space of dense graphs
• Packing tree factors in random and pseudo-random graphs
• Pancyclic subgraphs of random graphs
• On the number of hamilton cycles in a random graph
• Finding Hamilton cycles in random graphs with few queries
• Biased games on random boards
• Dirac's theorem for random regular graphs
• Hamiltonicity thresholds in Achlioptas processes
• Approximate Hamilton decompositions of random graphs
• The threshold for hamilton cycles in the square of a random graph
• Hamiltonicity in random graphs is born resilient
• Proper connection number of random graphs
• Robust Hamiltonicity of random directed graphs
• Packing arborescences in random digraphs
• Optimal packings of Hamilton cycles in sparse random graphs
• Bandwidth theorem for random graphs
• Cores of random graphs are born Hamiltonian
• Compatible Hamilton cycles in random graphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Resilience with respect to Hamiltonicity in random graphs
• Generating random graphs in biased maker-breaker games
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Edge-disjoint Hamilton cycles in random graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Conflict-free connection number of random graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Optimal covers with Hamilton cycles in random graphs
• On the Hamiltonicity of random bipartite graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• An algorithm for finding Hamilton paths and cycles in random graphs
• Note on matching preclusion number of random graphs
• Hitting time results for maker-breaker games
• Title not available (Why is that?)
• Hamiltonicity in random directed graphs is born resilient
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures
• Dirac's theorem for random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On covering expander graphs by Hamilton cycles
• On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three
• Bridged Hamiltonian cycles in sub-critical random geometric graphs

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

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