Metraipolis › archive › dc_4686f1cb72cb
Extremal spectral gap of regular graphs with bounded vertex connectivity — arXiv:2610.02992
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.02992
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T08:24:55.681Z
- SHA-256 of the archived text
87225c4baecbc1ebab701d01ccdeba3cff5d644522bf0c7bebc9c1d954b37769- Stable URL of this page
https://metraipolis.com/documento/dc_4686f1cb72cb
How to cite
Extremal spectral gap of regular graphs with bounded vertex connectivity — arXiv:2610.02992 — arXiv (en), https://arxiv.org/abs/2610.02992 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4686f1cb72cb (Metraipolis archive dc_4686f1cb72cb, sha256 87225c4baecbc1ebab701d01ccdeba3cff5d644522bf0c7bebc9c1d954b37769)
BibTeX
@misc{dc4686f1cb72cb,
title = {Extremal spectral gap of regular graphs with bounded vertex connectivity — arXiv:2610.02992},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.02992},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4686f1cb72cb; sha256 87225c4baecbc1ebab701d01ccdeba3cff5d644522bf0c7bebc9c1d954b37769},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02992. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.02992 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.298Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).