Cubic graphs with no eigenvalues in the interval (-1,1)
Krystal Guo Gordon F. Royle

[
    S. Skoupý and M. Štefaňák
    September 9, 2024
=============================



§ ABSTRACT 
We give a complete characterisation of the cubic graphs with no eigenvalues in the open interval (-1,1). There are two infinite families, one due to Guo and Mohar [Linear Algebra Appl. 449:68–75] the other due to Kollár and Sarnak [Communications of the AMS. 1,1–38], and 14 “sporadic” graphs on at most 32 vertices. This allows us to show that (-1,1) is a maximal spectral gap set for cubic graphs. Our techniques including examination of various substructure and an application of the classification of generalized line graphs.











MSC2020: Primary 05C50; Secondary 05C76.

keywords: graph eigenvalues, graph classification, graph spectra, spectral gap set





ntro2

xamples

roof



§ OPEN PROBLEMS AND FUTURE WORK



Lower and upper bounds on the maximum value of the HL-index among all graphs with given average degree are given in <cit.>. In the same paper, it is shown that a positive fraction of the eigenvalues of a subcubic graph lie in the interval [-√(2), √(2)].
It is still an open problem to show that the median eigenvalues of any cubic (or subcubic) graph, apart from the Heawood graph, are in the interval [-1,1]. 


An open sub-problem posed in <cit.> is to show that the median eigenvalues of subcubic planar graphs lie in [-1,1]; this problem was also collected in the recent collection of open problems in spectral graph theory, see <cit.>. It is true for subcubic, planar and  K_4-free graphs, as shown in <cit.>. 


The proofs in this paper rely heavily on the graph being cubic, and so do not apply to non-regular subcubic graphs. However we suspect that a similar result is true for non-regular subcubic graphs. In particular, we know two infinite families of non-regular subcubic graphs that arise from the Kollár-Sarnak graphs. The first family is obtained from k by deleting w_0, and second is obtained from k by deleting {w_0,b_k-1} (see <ref> for the vertex-naming convention). In addition we know four “sporadic” graphs on 8, 10, 14 and 18 vertices but we cannot currently rule out the existence of larger ones.







§ ACKNOWLEDGEMENTS
 

We would like to thank Brendan McKay who first pointed out the connection to positive semi-definite matrices and whose computations provided independent verification that the list of examples on up to 32 vertices is complete. 

K. Guo gratefully acknowledge the support of the Cheryl E. Praeger Visiting Research Fellowship, which facilitated the initiation of this research during a visit to the University of Western Australia.

plain


