Long paths and cycles in random subgraphs of graphs with large minimum degree1. Issue 2 (27th June 2013) - Krivelevich, Michael
Abstract For a given finite graph G of minimum degree at least k, let Gp be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if p≥ω/k for a function ω=ω(k) that tends to infinity as k does, then Gp asymptotically almost surely contains a cycle (and thus a path) of length at least (1−o(1))k, and (ii) if p≥(1+o(1))lnk/k, then Gp 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. © Wiley Periodicals, Inc. Random Struct. Alg., 46, 320–345, 2015