


















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} \approx 2.01980$, and $ρ$ is the unique real root of $x^3 = 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, \infty)$. 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_{α, β}(n)$ the maximum number of unit vectors in $\mathbb{R}^d$ where all pairwise inner products lie in $\{α, β\}$ with $-1 \le β< 0 \le α< 1$. Very recently Jiang, Tidor, Yao, Zhang and Zhao determined the limit of $N_{α, β}(d)/d$ as $d\to\infty$ when $α+ 2β< 0$ or $(1-α)/(α-β) \in \{1,\sqrt2,\sqrt3\}$, and they proposed a conjecture on the limit in terms of eigenvalue multiplicities of signed graphs. We establish their conjecture whenever $(1-α)/(α- β) < λ^*$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。