Skip to content
Preprint

Extremal spectral gap of regular graphs with bounded vertex connectivity

Oct 2026 · 0 citations · 27 references
Mathematics

Abstract

The well-known inequality of Fiedler ensures that the spectral gap $r-\lambda_2(G)$ of a connected non-complete $r$-regular graph $G$ is bounded from above by the vertex connectivity $\kappa(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 $r$-regular graph whose vertex connectivity is odd and no more than $2t-1$ has spectral gap at most $r-\min\bigl\{\xi(r,t),\nu(r,t)\bigr\}$ for some explicitly given functions $\xi(r,t)$ and $\nu(r,t)$. If $r\geq6t^2$, then this minimum equals $\xi(r,t)=\frac{r(2r-4t+5)}{2(r-t+2)}$. In particular, when $\kappa(G)=2t-1$, this gives $r-\lambda_2(G)<t=(\kappa(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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.