Sharp spectral bounds for the vertex-connectivity of regular graphs.

Let G be a connected d-regular graph and λ 2 (G) be the second largest eigenvalue of its adjacency matrix. Mohar and O (private communication) asked a challenging problem: what is the best upper bound for λ 2 (G) which guarantees that κ (G) ≥ t + 1 , where 1 ≤ t ≤ d - 1 and κ (G) is the vertex-connectivity of G, which was also mentioned by Cioabă. As a starting point, we determine a sharp bound for λ 2 (G) to guarantee κ (G) ≥ 2 (i.e., the case that t = 1 in this problem), and characterize all families of extremal graphs. [ABSTRACT FROM AUTHOR]