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$. They carried out a preliminary investigation of the subcubic case, exhibiting both infinite families and sporadic examples. In this paper, we complete this investigation by determining 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. 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 Sanark, established this maximality for connected cubic graphs. Our result generalizes their conclusion to the subcubic setting.

32 pages, 61 figures. This version fixes an error in Theorem 1 by removing one sporadic graph