Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
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)\ge r-κ(G)$ shows that $λ_2(G)<r-t$ forces $κ(G)\ge t+1$. The best such bound is known for $t=1$, by Zhang and Wang, and for $t=2$ with $r\ge4$, by Zhang. In this paper, for every $r\ge3$ and every integer $t$ with $2\le t\le r-1$, we give an upper bound on $λ_2(G)$ that forces an $r$-regular graph $G$ to satisfy $κ(G)\ge t+1$, and we determine exactly when this bound is best possible. For $\frac{r+2}{2}\le…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33064
curl -X POST /api/v1/records/arxiv/2610.33064/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33064/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'