Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult

Abstract

In 1976, Cameron, Goethals, Seidel, and Shult classified all the graphs whose smallest eigenvalue is at least $-2$ by relating such graphs to root systems that appear in the classification of semisimple Lie algebras. In this paper, extending their beautiful theorem, we give a complete classification of all connected graphs whose smallest eigenvalue lies in $(-{\lambda }^{\ast },-2)$, where ${\lambda }^{\ast }={\rho }^{1/2}+{\rho }^{-1/2}\approx 2.01980$, and $\rho$ is the unique real root of $x^3=x+1$. Our result is the first classification of infinitely many connected graphs with their smallest eigenvalue in $(-\lambda ,-2)$ for any constant $\lambda >2$.

29 pages, 12 figures

References in corpus (1)

• Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below