Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d ‐regular graph G on n vertices satisfies$$\lambda \leq{{(\log \, \log \, n)^2}\over {1000\, \log \, n \, (\log \, \log \, \log \, n)}}d$$ and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X ( G , S ), formed by choosing a set S of c log 5 n random generators in a group G of order n , is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003