Skip to content
Preprint

A complete characterization of graphs with second largest eigenvalue at most $(\sqrt5-1)/2$

Nov 2026 · 0 citations · 21 references
Mathematics

Abstract

In 1993, Cao and Hong posed the problem of characterizing graphs whose second largest adjacency eigenvalue is greater than $1/3$ and less than $(\sqrt5-1)/2$. Subsequent work extended the question to the non-strict bound. We give a complete structural characterization of connected graphs $G$ with $|V(G)|\ge2$ satisfying $\lambda_2(G)\le(\sqrt5-1)/2$. Their complements are described by disjoint unions of graphs from an explicit family with least adjacency eigenvalue at least $-(1+\sqrt5)/2$, 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\'c and Simi\'c that the bound $\lambda_2\le(\sqrt5-1)/2$ admits only finitely many minimal forbidden induced subgraphs.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.