Long paths and cycles in random subgraphs of graphs with large minimum degree1. Issue 2 (27th June 2013) - Krivelevich, Michael; Lee, Choongbum; Sudakov, Benny
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734k4g1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≥ω/k</alternatives> for a function <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734k4cc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ω=ω(k)</alternatives> that tends to infinity as k does, then Gp asymptotically almost surely contains a cycle (and thus a path) of length at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734k498" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1−o(1))k</alternatives>, and (ii) if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734k48q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≥(1+o(1))lnk/k</alternatives>, 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