Skip to main content
1 of 3

The answer to your question is to look for literature on the spectrum of the graph adjacency matrix, with particular attention paid to its nullity (multiplicity of eigenvalue zero). This is due to Claim 1.

One very interesting property is the link between the nullity of $A$ and the chromatic number of the matrix. In particular, there is something known as the rank-coloring conjecture. Graphs with a large $m_1(L)$ will have a low-rank $A$, and thus have a lower chromatic number.

Sample refs below. More can be found via google. Brouwer, Andries E., and Willem H. Haemers. Spectra of graphs. Springer, 2011. A.A. Razborov, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Discrete Mathematics, Volume 108, Issues 1–3, 28 October 1992, Pages 393-396, ISSN 0012-365X, http://dx.doi.org/10.1016/0012-365X(92)90691-8.

Notations. The normalized graph Laplacian is defined $L=I-D^{-1/2}AD^{-1/2}$, where $D$ and $A$ are the usual degree and adjacency matrices. Let us write the multiplicity of an eigenvalue $\lambda$ in matrix $M$ as $m_{\lambda}(M)$.

Claim 1. For any graph with no isolated vertices, the following equality holds between the normalized Laplacian, $L$, and the Adjacency matrix, $A$, $$m_1(L) = m_0(A).$$

Proof. Let us expand the eigenvalue identity for $\lambda=1$, and substitute the definition of the matrix

$$\begin{align*} Lv & =v\\ \implies v-D^{-1/2}AD^{-1/2}v & =v\\ \implies D^{-1/2}AD^{-1/2}v & =0\\ \implies Ax & =0 \end{align*}$$

where we have introduced $x:=D^{-1/2}v$. Clearly, any $x$ that satisfies this comes from $x\in\mathrm{null}(A)$, and $X\ni x$ must necessarily satisfy $X=\mathrm{null}(A)$.

Next, let us write out the space containing $v$. We have assumed that the graph has no isolated, i.e. degree-zero vertices, such that $D^{-1/2}$ is necessarily full-rank (i.e. a bijective mapping) with inverse $D^{1/2}$. If $x \in X$, then $v\in D^{1/2}X$.

Putting these together, we have $$m_1(L)\equiv\mathrm{dim}(D^{1/2}X)\\=\mathrm{dim}(X)\equiv\mathrm{dim}(\mathrm{null}(A))\equiv m_0(A)$$ QED.