Edge-connectivity in regular multigraphs from eigenvalues

Let $G$ be a $d$-regular multigraph, and let $λ_2(G)$ be the second largest eigenvalue of $G$. In this paper, we prove that if $λ_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 $λ_2(G)<d-t$, and in fact when $λ_2(G)<d-t+1$ if $t$ is odd.

No reviews yet.

No comments yet.