Edge-connectivity in regular multigraphs from eigenvalues

Original · EN

Let G be a d-regular multigraph, and let λ₂(G) be the second largest eigenvalue of G. In this paper, we prove that if λ₂(G) < d-1+√9d²-10d+174, then G is 2-edge-connected. Furthermore, for t≥2 we show that G is (t+1)-edge-connected when λ₂(G)<d-t, and in fact when λ₂(G)<d-t+1 if t is odd.