Premium
Sparse pseudo‐random graphs are Hamiltonian
Author(s) -
Krivelevich Michael,
Sudakov Benny
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10065
Subject(s) - mathematics , combinatorics , random graph , cayley graph , hamiltonian (control theory) , random regular graph , hamiltonian path , discrete mathematics , eigenvalues and eigenvectors , graph , line graph , 1 planar graph , physics , mathematical optimization , quantum mechanics
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