A complete characterization of graphs with second largest eigenvalue at most
arXiv:2611.02005
Abstract
In 1993, Cao and Hong posed the problem of characterizing graphs whose second largest adjacency eigenvalue is greater than and less than . Subsequent work extended the question to the non-strict bound. We give a complete structural characterization of connected graphs with satisfying . Their complements are described by disjoint unions of graphs from an explicit family with least adjacency eigenvalue at least , possibly together with a cone or a thin or thick spider constructed from disjoint unions of members of the same family, subject to explicit numerical inequalities. This provides a positive characterization of the class, going beyond the classical result of Cvetković and Simić that the bound admits only finitely many minimal forbidden induced subgraphs.
arXiv comment20 pages, 2 figures