How many random edges make a graph Hamiltonian?

DOI10.1007/BF02579348zbMath0521.05056WikidataQ105583337 ScholiaQ105583337MaRDI QIDQ1055442

Eli Shamir

Publication date: 1983

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian paththreshold edge probability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Eulerian and Hamiltonian graphs (05C45)

Related Items

Finding Hamilton cycles in sparse random graphs ⋮ An algorithm for finding Hamilton paths and cycles in random graphs ⋮ Finding tight Hamilton cycles in random hypergraphs faster ⋮ A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time ⋮ A simple linear expected time algorithm for finding a Hamilton path ⋮ Tight Hamilton cycles in random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On factors in random graphs
• The longest path in a random graph
• One-factor in random graphs based on vertex choice
• Hamiltonian circuits in random graphs
• On the existence of Hamiltonian cycles in a class of random graphs
• On the strength of connectedness of a random graph