On the order of regular graphs with fixed second largest eigenvalue

2018/09/06 by Yang, Jae Young, Koolen, Jack H. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.01888

Abstract

Let v(k, λ) be the maximum number of vertices of a connected k-regular graph with second largest eigenvalue at most λ. The Alon-Boppana Theorem implies that v(k, λ) is finite when k > (λ² + 4)/(4). In this paper, we show that for fixed λ≥1, there exists a constant C(λ) such that 2k+2 ≤ v(k, λ) ≤ 2k + C(λ) when k > (λ² + 4)/(4).

Cited by

• The non-existence of some Moore polygons and spectral Moore bounds

Related

• Maximizing the order of a regular graph of given valency and second eigenvalue
• A best bound for λ₂(G) to guarantee κ(G) ≥ 2
• A spectral version of the Moore problem for bipartite regular graphs
• The non-existence of some Moore polygons and spectral Moore bounds
• Spectral Bounds for the Connectivity of Regular Graphs with Given Order