On the number of Hamilton cycles in pseudo-random graphs
The electronic journal of combinatorics, Tome 19 (2012) no. 1
We prove that if $G$ is an $(n,d,\lambda)$-graph (a $d$-regular graph on $n$ vertices, all of whose non-trivial eigenvalues are at most $\lambda)$ and the following conditions are satisfied:$\frac{d}{\lambda}\ge (\log n)^{1+\epsilon}$ for some constant $\epsilon>0$; $\log d\cdot \log\frac{d}{\lambda}\gg \log n$, then the number of Hamilton cycles in $G$ is $n!\left(\frac{d}{n}\right)^n(1+o(1))^n$.
@article{10_37236_1177,
author = {Michael Krivelevich},
title = {On the number of {Hamilton} cycles in pseudo-random graphs},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {1},
doi = {10.37236/1177},
zbl = {1243.05141},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1177/}
}
Michael Krivelevich. On the number of Hamilton cycles in pseudo-random graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/1177
Cité par Sources :