























In this paper, we study the maximum order $v(k,θ)$ of a connected $k$-regular graph whose second largest eigenvalue is at most $θ$. From Alon-Boppana and Serre, we know that $v(k,θ)$ is finite when $θ< 2\sqrt{k-1}$ while the work of Marcus, Spielman, and Srivastava implies that $v(k,θ)$ is infinite if $θ\geq 2\sqrt{k-1}$. Cioabă, Koolen, Nozaki, and Vermette obtained a general upper bound on $v(k, θ)$ via Nozaki's linear programming bound and determined many values of $v(k,θ)$. The graphs attaining this bound are distance-regular and are called Moore polygons. Damerell and Georgiacodis proved that there are no Moore polygons of diameter $6$ or more. For smaller diameters, there are infinitely many Moore polygons. We complement these results by proving two nonexistence results for Moore polygons with specific parameters. We also determine new values of $v(k,θ)$: $v(4, \sqrt{2}) = 14$ and $v(5, \sqrt{2}) = v(5,\sqrt{5}-1)=16$. The former is achieved by the co-Heawood graph, and the latter by the folded $5$-cube. We verify that any connected $5$-regular graph with second eigenvalue $λ_2$ exceeding $1$ satisfies $λ_2 \geq \sqrt{5} - 1$, and that the unique $5$-regular graph attaining equality in this bound has $10$ vertices. We prove a stronger form of a 2015 conjecture of Kolokolnikov related to the second eigenvalue of cubic graphs of given order, and observe that other recent results on the second eigenvalue of regular graphs are consequences of the general upper bound theorem on $v(k,θ)$ mentioned above.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。