Approximate Hamilton decompositions of random graphs

Abstract

Abstract We show that if pn ≫ log n the binomial random graph G n , p has an approximate Hamilton decomposition. More precisely, we show that in this range G n , p contains a set of edge‐disjoint Hamilton cycles covering almost all of its edges. This is best possible in the sense that the condition that pn ≫ log n is necessary. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012