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.

Back to all abstracts