Let $G = (V, E)$ be a finite graph and let $\Delta$ denote its Laplacian (here we take the convention that the Laplacian is positive semidefinite). For simplicity name the vertices $1, 2, ... n$. Then $\Delta$ is the matrix associated to the quadratic form
$$q(x_1, ... x_n) = \sum_{(i, j) \in E} (x_i - x_j)^2$$
which one might call the Dirichlet energy. Recall that, for an appropriate change of variables, such a quadratic form can be written as
$$q(z_1, ... z_n) = \sum_i \lambda_i z_i^2$$
where $\lambda_i$ are the eigenvalues of $\Delta$. Thus to determine the multiplicity of the zero eigenvalue it suffices to determine when $q$ can be zero. But from the first expression it should be clear that $q = 0$ if and only if $x_i = x_j$ whenever $(i, j) \in E$; that is, whenever $(x_1, ... x_n)$ determines a function
$$x : V \to \mathbb{R}$$
which is constant on each connected component of $G$. The dimension of this space of functions is clearly the number of connected components of $G$, and the conclusion follows.
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$.
Best Answer
The following excerpt is taken from the book Spectra and pseudospectra of Trefethen and Embree, first page.
If the eigenvalues of $A$ are $\lambda_1, \lambda_2,\ldots,\lambda_n$, then the eigenvalues of $A^k$ are, unsurprisingly, $\lambda_1^k, \lambda_2^k, \ldots, \lambda_n^k$. In particular, they have modulus $$ |\lambda_1|^k, |\lambda_2|^k, \ldots, |\lambda_n|^k.$$ Now suppose that $|\lambda_1|>|\lambda_j|$ for all $j=2,\ldots,n$. Then, obviously, $$ \frac{|\lambda_j|^k}{|\lambda_1|^k}\to 0.$$ This shows that, as $k\to \infty$, the non-dominant eigenvalues are asymptotically negligible. Thus, they have lesser importance in any situation in which the computation of $A^k$ is required. As Trefethen and Embree point out, these situations are the most important in applications.