Long cycles in random subgraphs of graphs with large minimum degree

Abstract

Let $G$ be any graph of minimum degree at least $k$, and let $G_p$ be the random subgraph of $G$ obtained by keeping each edge independently with probability $p$. Recently, Krivelevich, Lee and Sudakov showed that if $pk\to \infty$ then with probability tending to 1 $G_p$ contains a cycle of length at least $(1-o(1))k$. We give a much shorter proof of this result, also based on depth-first search.

4 pages, 1 figure; figure reoriented

Cited by in corpus (5)

• Hamilton Cycles in Random Graphs: a bibliography
• The threshold probability for long cycles
• Long paths and cycles in random subgraphs of H-free graphs
• Large complete minors in random subgraphs
• Expansion, long cycles, and complete minors in supercritical random subgraphs of the hypercube