# Large regular graphs of given valency and second eigenvalue

###
Hiroshi Nozaki

Aichi University of Education

PDF

**Minisymposium:**
SPECTRAL GRAPH THEORY

**Content:**
It is known that for any given integer $k\geq 3$ and real number $\lambda<2\sqrt{k-1}$, there are only finitely many $k$-regular graphs whose second largest eigenvalue is at most $\lambda$. In this talk, we give a new upper bound for the order of such a graph for given $k$ and $\lambda$. The main tool is the linear programming method for regular graphs. A graph which satisfies $g\geq 2d$ attains this upper bound for some
$k$ and $\lambda$, where $g$ is the girth and $d$ is the number of distinct eigenvalues.
This is a joint work with Cioaba, Koolen, and Vermette.