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 vertex connectivity 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) \le \kappa(G)$foranon-completesimplegraph$G$;forthisreason$\mu_2(G)$iscalledthe\mathrm{"}algebraicconnectivity\mathrm{"}of$G$. We extend his result to multigraphs. For a pair of vertices $u$ and $v$, let $m(u,v)$ be the number of edges with endpoints $u$ and $v$. For a vertex $v$, let $m(v)=\max_{u \in N(v)} m(v,u)$,where$N(v)$isthesetofneighborsof$v$,andlet$m(G)=\max_{v \in V(G)} m(v)$\mathrm{.}Weprovethatforanymultigraph$G$ whose underlying graph is not a complete graph, ${\mu }_2(G)\le \kappa (G)m(G)$. We also prove that for any $d$-regular multigraph $G$ whose underlying graph is not the complete graph with 2 vertices, if ${\mu }_2(G)>\frac{d}{4}$, then $G$ is 2-connected. For $t\ge 2$ and infinitely many $d$, we construct $d$-regular multigraphs $H$ with ${\mu }_2(H)=d$, $\kappa (H)=t$, and $m(H)=\frac{d}{t}$. These graphs show that the inequality ${\mu }_2(G)\le \kappa (G)m(G)$ is sharp. In addition, we prove that if $G$ is a $d$-regular multigraph whose underlying graph is not a complete graph, then ${\mu }_2(G)\le d$; equality holds for the graphs in the construction.