The non-existence of some Moore polygons and spectral Moore bounds
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Attainable bounds for algebraic connectivity and maximally connected regular graphsJournal of Graph Theory, 2024
- Approximately strongly regular graphsDiscrete Mathematics, 2023
- On the spectrum and linear programming bound for hypergraphsEuropean Journal of Combinatorics, 2022
- Recent Progress on Graphs with Fixed Smallest Adjacency Eigenvalue: A SurveyGraphs and Combinatorics, 2021
- Maximizing algebraic connectivity for certain families of graphsLinear Algebra and its Applications, 2015
- Uniqueness of the 120-point spherical 11-design in four dimensionsArchiv der Mathematik, 2001
- Fast generation of regular graphs and construction of cagesJournal of Graph Theory, 1999
- Eigenvalues and expandersCombinatorica, 1986
- On the spectra of certain distance-regular graphsJournal of Combinatorial Theory, Series B, 1979
- Spherical codes and designsGeometriae Dedicata, 1977