What can we say about the graph when many eigenvalues of the Laplacian are equal to 1?

Solution 1:

I can make two sort of hand-wavy observations. From basic linear algebra properties we know that given a matrix $ \mathbf{L} $ \begin{equation} \sum_{i}d_{i}= \sum_{i}\lambda_{i} \end{equation}

where $ \lambda $ are the eigenvalues, and $ d $ are the the diagonal elements of your matrix $ \mathbf{L} $.

The elements on the diagonal of the Laplacian correspond to the degrees of the vertices. Assuming no isolated vertices and that the graph is simple (i.e weights are either $0$ or $1$), $ d_{i} \geq 1 $.

If most of your eigenvalues are equal to $1$, then their sum is also likely a small number. That means that the sum of degrees is also a small number, which means that your graph is probably sparsely connected.

The next observation has to do with star graphs. In general, complete bipartite graphs with $n$ and $m$ vertices on each group respectively, have Laplacian eigenvalues:

• $n$ with multiplicity $m-1$
• $m$ with multiplicity $n-1$
• $0$ with multiplicity $1$
• $m+n$ with multiplicity 1

Consider the star graph below which is a complete bipartite graph with $n=1$ and $m=8$

Its eigenvalues are $1$ with multiplicity $7$, $0$ with multiplicity $1$ and $9$ with multiplicity $1$.

So, if your graph contains starlike subgraphs, then your Laplacian is going to have a bunch of $1$-eigenvalues. I include two examples below (the random isolated component belongs to the graph on the right).

.

Both of these graphs have eigenvalue $1$ with multiplicity $9$.