Approximate Hamilton decompositions of random graphs |
| |
| Authors: | Fiachra Knox Daniela Kühn Deryk Osthus |
| |
| Affiliation: | School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK |
| |
| Abstract: | We show that if pn ? log n the binomial random graph Gn,p has an approximate Hamilton decomposition. More precisely, we show that in this range Gn,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 |
| |
| Keywords: | random graphs Hamilton cycles Hamilton decomposition |
|
|
