On the Number of Hamilton Cycles in Pseudo-Random Graphs

Abstract

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:

1. $\frac{d}{\lambda}\ge (\log n)^{1+\epsilon}$ for some constant $\epsilon>0$;
2. $\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$.