View PDF HTML (experimental)

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.

Submission history

From: Zilin Jiang [view email]
[v1] Sun, 4 Jan 2026 11:07:02 UTC (25 KB)
[v2] Wed, 29 Apr 2026 20:46:39 UTC (27 KB)
[v3] Fri, 28 Aug 2026 01:34:18 UTC (304 KB)