Approximate Hamilton decompositions of random graphs
Approximate Hamilton decompositions of random graphs
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 …