Extremal spectral gap of regular graphs with bounded vertex connectivity
Abstract
The well-known inequality of Fiedler ensures that the spectral gap r−λ2(G) of a connected non-complete r-regular graph G is bounded from above by the vertex connectivity κ(G) of G. We prove that, for integers t≥2 and r>2t2, every connected r-regular graph with vertex connectivity at most 2t has spectral gap at most 1/2(r+t+2−√((r−t+2)2−4t(t−1))). We show that this bound is nearly optimal for each fixed t ≥ 2 and sufficiently large r > 2t2 such that r+1 is divisible by t. We further prove that if r>(2t−1)(2t−2), then every connected r-regular graph whose vertex connectivity is odd and no more than 2t−1 has spectral gap at most r−min{ξ(r,t),ν(r,t)} for some explicitly given functions ξ(r,t) and ν(r,t). If r≥6t2, then this minimum equals ξ(r,t)=(r(2r−4t+5))/(2(r−t+2)). In particular, when κ(G)=2t−1, this gives r−λ2(G)<t=(κ(G)+1)/2, which improves Fiedler's bound by nearly a factor of two. Our upper bounds in their parameter ranges improve two known bounds on the spectral gap of regular graphs.
Related
- Spectral Extremal 1-Planar Graphs with Bounded Pentagon Packing
- Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
- Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
BibTeX
@misc{wang2026extremal,
title = {{Extremal spectral gap of regular graphs with bounded vertex connectivity}},
author = {Yu Wang and Sanming Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02992},
eprint = {2610.02992},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02992},
}
RIS
TY - UNPB
TI - Extremal spectral gap of regular graphs with bounded vertex connectivity
AU - Yu Wang
AU - Sanming Zhou
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02992
UR - https://arxiv.org/abs/2610.02992
AB - The well-known inequality of Fiedler ensures that the spectral gap r−λ_2(G) of a connected non-complete r-regular graph G is bounded from above by the vertex connectivity κ(G) of G. We prove that, for integers t≥2 and r>2t^2, every connected r-regular graph with vertex connectivity at most 2t has spectral gap at most 1/2(r+t+2−√((r−t+2)^2−4t(t−1))). We show that this bound is nearly optimal for each fixed t ≥ 2 and sufficiently large r > 2t^2 such that r+1 is divisible by t. We further prove that if r>(2t−1)(2t−2), then every connected r-regular graph whose vertex connectivity is odd and no more than 2t−1 has spectral gap at most r−min{ξ(r,t),ν(r,t)} for some explicitly given functions ξ(r,t) and ν(r,t). If r≥6t^2, then this minimum equals ξ(r,t)=(r(2r−4t+5))/(2(r−t+2)). In particular, when κ(G)=2t−1, this gives r−λ_2(G)<t=(κ(G)+1)/2, which improves Fiedler's bound by nearly a factor of two. Our upper bounds in their parameter ranges improve two known bounds on the spectral gap of regular graphs.
ER -