On the spectral gap and the diameter of Cayley graphs

Abstract

We obtain a new bound connecting the first non--trivial eigenvalue of the Laplace operator of a graph and the diameter of the graph, which is effective for graphs with small diameter or for graphs, having the number of maximal paths comparable to the expectation.

arXiv comment22 pages