SIAM Journal on Discrete Mathematics · 2013 · 34 citations · 23 references
Natural SciencesMathematicsCombinatoricsProbability TheoryStochastic ProcessesGraph TheoryMarkov ProcessesProbabilistic CombinatoricsHamiltonian CyclesHamiltonicity In Random GraphsHitting TimesRandom Graph ModelsRandom Graph ProcessesRandom Graph TheoryRandom GraphsSparse Random Graphs
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.
23