Algebraic connectivity of multigraphs

Suil O

Published 2016-03-12Version 1

Let $\mu_2(G)$ be the second smallest Laplacian eigenvalue of a graph $G$, and let $\kappa(G)$ be the minimum size of a vertex set $S$ such that $G-S$ is disconnected. Fiedler proved that $\mu_2(G) \le \kappa(G)$ for a non-complete simple graph $G$, for this reason $\mu_2(G)$ is called the "algebraic connectivity" 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)$ is the set of neighbors of $v$, and let $m(G)=\max_{v \in V(G)} m(v)$. We prove that for any multigraph $G$, except when $G$ is a multigraph obtained from a complete graph by duplicating edges, $\mu_2(G) \le \kappa(G) m(G)$. We also prove that for a $d$-regular multigraph $G$, except for the 2-vertex $d$-regular multigraph, if $\mu_2(G) > \frac d4$, then $G$ is 2-connected. For $t\ge2$ and infinitely many $d$, we construct $d$-regular multigraphs $H$ with $\mu_2(H)=d$, $\kappa(H)=t$, and $m(H)=\frac dt$. 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, except for a graph obtained from a complete graph by duplicating edges, then $\mu_2(G) \le d$, equality holds for the graphs in the construction.