Subcubic graphs without eigenvalues in $(-1,1)$

Abstract

Guo and Royle recently classified the connected cubic graphs without eigenvalues of their adjacency matrix in the open interval $(-1,1)$, and raised the question of extending their classification to graphs of maximum degree at most $3$. Together with their cubic classification, our result fully answers this question by characterizing all connected subcubic graphs that are not cubic and have no eigenvalues in $(-1,1)$. We show that exactly two infinite families and seven sporadic examples occur, and that every sporadic graph has at most $18$ vertices. To obtain this complete classification, we build a bridge between spectral graph theory and structural graph theory for graphs whose adjacency matrices, after selected diagonal entries are changed to $-1$, have smallest eigenvalue at least $-2$. This generalizes the classical theorem of Cameron, Goethals, Seidel and Shult for graphs with smallest eigenvalue at least $-2$. As a consequence, we prove that $(-1,1)$ is a maximal spectral gap set for the class of connected subcubic graphs. Guo and Royle, answering a question of Kollár and Sarnak, established this maximality for connected cubic graphs. Our result generalizes their conclusion to the subcubic setting.

arXiv comment34 pages, 8 figures and 54 diagrams; revised version gives purely structural formulations of the classification theorems and adds ancillary Lean formalization