When is the algebraic connectivity a simple eigenvalue of the graph Laplacian？

Question

For a simple graph, we know that the second smallest eigenvalue of its Laplacian matrix is called the algebraic connectivity.

My question is when the algebraic connectivity is a simple eigenvalue, or what type of graph structure can guarantee this fact?

Thanks!

Answer 1

Guo, Feng and Zhang give some examples of trees with simple connectivity in On the multiplicity of laplacian eigenvalues of graphs. More generally, multiplicity of algebraic connectivity is discussed in The perturbed Laplacian matrix of a graph by Bapat, Pati and Kirkland. But if you are hoping for a simple condition that guarantees simplicity there isn't any. For example, their Corollary 8 states that the algebraic connectivity is simple if there is a cut vertex with exactly two Perron components.

Let $v$ be a cut vertex of a connected graph $G$, removing which splits it into connected components $G_i$. Such a component is called Perron component if the least eigenvalue of the principal submatrix of the Laplacian matrix of $G$ corresponding to $G_i$ is minimal among the least eigenvalues of these components. They prove that this happens if and only if the least eigenvalue does not exceed the algebraic connectivity of $G$ itself.