How many random edges make a dense graph hamiltonian?

Abstract

This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding $\Theta (n)$ random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

7 pages, 1 figure

Cited by in corpus (4)

• Hamilton Cycles in Random Graphs: a bibliography
• An O(n) time algorithm for finding Hamilton cycles with high probability
• Finding tight Hamilton cycles in random hypergraphs faster
• Tight Hamilton cycles in random hypergraphs