Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below

The smallest eigenvalue of a graph is the smallest eigenvalue of its adjacency matrix. We show that the family of graphs with smallest eigenvalue at least -λ can be defined by a finite set of forbidden induced subgraphs if and only if λ < λ ^* , where λ ^* = ρ 1/2 + ρ -1/2 ≈ 2.01980 , and ρ is the unique real root of x³ = x + 1 . This resolves a question raised by Bussemaker and Neumaier. As a byproduct, we find all the limit points of smallest eigenvalues of graphs, supplementing Hoffman’s work on those limit points in [-2, ∞ ) . We also prove that the same conclusion about forbidden subgraph characterization holds for signed graphs. Our impetus for the study of signed graphs is to determine the maximum cardinality of a spherical two-distance set with two fixed angles (one acute and one obtuse) in high dimensions. Denote by Nα , β(d) the maximum number of unit vectors in Rᵈ where all pairwise inner products lie in \α , β \ with -1 ≤ β < 0 ≤ α < 1 . Very recently Jiang, Tidor, Yao, Zhang, and Zhao determined the limit of Nα , β(d)/d as d→ ∞ when α + 2β < 0 or (1-α )/(α -β ) ∈ \1,√ 2,√ 3\ , and they proposed a conjecture on the limit in terms of eigenvalue multiplicities of signed graphs. We establish their conjecture whenever (1-α )/(α - β ) < λ ^* .