Maximizing the order of a regular graph of given valency and second eigenvalue

Abstract

From Alon and Boppana, and Serre, we know that for any given integer $k\ge 3$ and real number $\lambda <2\sqrt{k-1}$, there are finitely many $k$-regular graphs whose second largest eigenvalue is at most $\lambda$. In this paper, we investigate the largest number of vertices of such graphs.

SIAM Journal of Discrete Mathematics 30, 1509-1525, (2016)