




















Given any graph $G$, the (adjacency) spread of $G$ is the maximum absolute difference between any two eigenvalues of the adjacency matrix of $G$. In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers $n$, the $n$-vertex graph $G$ that maximizes spread is the join of a clique and an independent set, with $\lfloor 2n/3 \rfloor$ and $\lceil n/3 \rceil$ vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all $n$ sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over $\mathscr{L}^2[0,1]$. The second conjecture claims that for any fixed $e\leq n^2/4$, if $G$ maximizes spread over all $n$-vertex graphs with $e$ edges, then $G$ is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we exhibit an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower order error terms.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。