Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
Abstract
Let λ2(G) and κ(G) denote the second largest adjacency eigenvalue and the vertex-connectivity of a graph G. For a non-complete r-regular graph G, Fiedler's inequality λ2(G)≥ r−κ(G) shows that λ2(G)<r−t forces κ(G)≥ t+1. The best such bound is known for t=1, by Zhang and Wang, and for t=2 with r≥4, by Zhang. In this paper, for every r≥3 and every integer t with 2≤ t≤ r−1, we give an upper bound on λ2(G) that forces an r-regular graph G to satisfy κ(G)≥ t+1, and we determine exactly when this bound is best possible. For (r+2)/2≤ t≤ r−1, Fiedler's bound r−t is already best possible. For 2≤ t<(r+2)/2, it is replaced by one of two explicit algebraic numbers, and the sign of an explicit polynomial W(r,t), which never vanishes, decides which one applies. Each of the two numbers is attained exactly when (r,t) satisfies an explicit arithmetic condition, and every extremal graph then consists of two cliques and an independent cut of size t. In this range our bound also improves a bound of Zhang that holds for every such t.
Related
- Planar graphs whose second largest eigenvalue does not exceed 1
- A complete characterization of graphs with second largest eigenvalue at most (√5−1)/2
- Large deviations for the largest eigenvalue of a polynomial in Gaussian matrices
- Staircase phase transitions for the largest eigenvalue of heavy-tailed sample correlation matrices
- On the asymptotic distribution of the largest eigenvalue of unbalanced complex Jacobi ensembles
BibTeX
@misc{suil2026second,
title = {{Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs}},
author = {Suil O and Lukai Sui},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33064},
eprint = {2610.33064},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33064},
}
RIS
TY - UNPB
TI - Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
AU - Suil O
AU - Lukai Sui
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.33064
UR - https://arxiv.org/abs/2610.33064
AB - Let λ_2(G) and κ(G) denote the second largest adjacency eigenvalue and the vertex-connectivity of a graph G. For a non-complete r-regular graph G, Fiedler's inequality λ_2(G)≥ r−κ(G) shows that λ_2(G)<r−t forces κ(G)≥ t+1. The best such bound is known for t=1, by Zhang and Wang, and for t=2 with r≥4, by Zhang. In this paper, for every r≥3 and every integer t with 2≤ t≤ r−1, we give an upper bound on λ_2(G) that forces an r-regular graph G to satisfy κ(G)≥ t+1, and we determine exactly when this bound is best possible. For (r+2)/2≤ t≤ r−1, Fiedler's bound r−t is already best possible. For 2≤ t<(r+2)/2, it is replaced by one of two explicit algebraic numbers, and the sign of an explicit polynomial W(r,t), which never vanishes, decides which one applies. Each of the two numbers is attained exactly when (r,t) satisfies an explicit arithmetic condition, and every extremal graph then consists of two cliques and an independent cut of size t. In this range our bound also improves a bound of Zhang that holds for every such t.
ER -