arXiv:2610.33064v1 Announce Type: new Abstract: Let $\lambda_2(G)$ and $\kappa(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 $\lambda_2(G)\ge r-\kappa(G)$ shows that $\lambda_2(G)<r-t$ forces $\kappa(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 $\lambda_2(G)$ that forces an $r$-regular graph $G$ to satisfy $\kappa(G)\ge t+1$, and we determine exactly when this bound is best possible. For $\frac{r+2}{2}\le t\le r-1$, Fiedler's bound $r-t$ is already best possible. For $2\le t<\frac{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$.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page