On the order of regular graphs with fixed second largest eigenvalue

Abstract

Let $v(k,\lambda )$ be the maximum number of vertices of a connected $k$-regular graph with second largest eigenvalue at most $\lambda$. The Alon-Boppana Theorem implies that $v(k,\lambda )$ is finite when $k>\frac{{\lambda }^2+4}{4}$. In this paper, we show that for fixed $\lambda \ge 1$, there exists a constant $C(\lambda )$ such that $2k+2\le v(k,\lambda )\le 2k+C(\lambda )$ when $k>\frac{{\lambda }^2+4}{4}$.

13 pages