Edge-connectivity in regular multigraphs from eigenvalues

Suil O

Published 2014-09-22Version 1

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\ge2$ 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.