| Abstract: | 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  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 log5 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 |
