On the Number of Hamilton Cycles in Sparse Random Graphs
Authors:
- Roman GlebovRGRoman Glebov
- Michael KrivelevichMKMichael Krivelevich
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 27 (1) , 27-42
Abstract
We prove that the number of Hamilton cycles in the random graph $G(n,p)$ is $n!p^n(1+o(1))^n$ asymptotically almost surely (a.a.s.), provided that $p\geq \frac{\ln n+\ln\ln n+\omega(1)}{n}$. Furthermore, we prove the hitting time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree $2$ creates $(\frac{\ln n}{e})^n(1+o(1))^n$ Hamilton cycles a.a.s.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Hitting time results for Maker‐Breaker gamesRandom Structures & Algorithms, 2011
- On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random GraphsSIAM Journal on Discrete Mathematics, 2011
- Hamilton cycles in highly connected and expanding graphsCombinatorica, 2009
- A sharp threshold for the Hamilton cycle Maker–Breaker gameRandom Structures & Algorithms, 2008
- On two Hamilton cycle problems in random graphsIsrael Journal of Mathematics, 2008
- On packing Hamilton cycles in -regular graphsJournal of Combinatorial Theory, Series B, 2005
- Hamilton cycles in random subgraphs of pseudo-random graphsDiscrete Mathematics, 2002
- Random Regular Graphs: Asymptotic Distributions and ContiguityCombinatorics, Probability and Computing, 1995
- On the number of hamilton cycles in a random graphJournal of Graph Theory, 1989
- An algorithm for finding hamilton paths and cycles in random graphsCombinatorica, 1987