The second largest eigenvalue and vertex-connectivity of regular multigraphs

Let mu(2)(G) be the second smallest Laplacian eigenvalue of a graph G. The vertexconnectivity of G, written kappa(G), is the minimum size of a vertex set S such that G- S is disconnected. Fiedler proved that mu(2)(G) <= kappa(G) for a non-complete simple graph G; for this reason mu(2)(G) is called the "algebraic connectivity'' of G. His result can be extended to multigraphs: for any multigraph G who underlying graph is not a complete graph, we have mu(2)(G) <= kappa (G)m(G), where for a pair of vertices u and v, let m(u, v) be the number of edges with endpoints u and v and m(G) = max((u,v)epsilon E(G)) m(v, u). Let lambda(2)(G) be the second largest eigenvalue of a graph G. We also prove that for any dregular multigraph G whose underlying graph is not the complete graph with 2 vertices, if lambda(2)(G) < 3/4 d, then G is 2-connected. For t >= 2 and infinitely many d, we construct dregular multigraphs H with lambda(2)(H) = 0, epsilon(H) = t, and m(H) = d/t. These graphs show that the inequality mu(2)(G) = kappa(G)m(G) is sharp and that there is no upper bound for.2(G) in a d-regular multigraph G to guarantee a certain vertex-connectivity greater than or equal to 3. (C) 2019 Elsevier B.V. All rights reserved.