Edge-connectivity in regular multigraphs from eigenvalues

Abstract

Let $G$ be a $d$-regular multigraph, and let ${\lambda }_2(G)$ be the second largest eigenvalue of $G$. In this paper, we prove that if ${\lambda }_2(G)<\frac{d-1+\sqrt{9d^2-10d+17}}{4}$, then $G$ is 2-edge-connected. Furthermore, for $t\ge 2$ we show that $G$ is $(t+1)$-edge-connected when ${\lambda }_2(G)<d-t$, and in fact when ${\lambda }_2(G)<d-t+1$ if $t$ is odd.

11 pages, 2 figures (in press, Linear Algebra and its Application)