Extremal spectral gap of regular graphs with bounded vertex connectivity
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\geq2$ and $r>2t^2$, every connected $r$-regular graph with vertex connectivity at most $2t$ has spectral gap at most $\frac{1}{2}(r+t+2-\sqrt{(r-t+2)^2-4t(t-1)})$. We show that this bound is nearly optimal for each fixed $t \ge 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02992
curl -X POST /api/v1/records/arxiv/2610.02992/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02992/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'