Long paths and cycles in random subgraphs of graphs with large minimum degree

Abstract: For a given finite graph

G

of minimum degree at least

k

, let

G_{p}

be a random subgraph of

G

obtained by taking each edge independently with probability

p

. We prove that (i) if

p g e o m e g a / k

for a function

o m e g a = o m e g a (k)

that tends to infinity as

k

does, then

G_{p}

asymptotically almost surely contains a cycle (and thus a path) of length at least

(1 - o (1)) k

, and (ii) if

p g e (1 + o (1)) l n k / k

, then

G_{p}

asymptotically almost surely contains a path of length at least

k

. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking

G

to be the complete graph on

k + 1

vertices.

This page was built for publication: Long paths and cycles in random subgraphs of graphs with large minimum degree