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.

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.

To answer the part about symmetry. A matrix with $\pm$ adjacency eigenvalue pairs (i.e. symmetric about zero) is bipartite, i.e. 2-colorable, and these become symmetric about 1 in the normalized Laplacian spectrum (this is a simple corollary of the proof below). As a graph becomes more bipartite, its Laplacian spectrum becomes more symmetric about 1.

In other words, you have two sets of nodes in your graphs which are (for the most part) disconnected from each other. For instance, your graph could represent the email exchanges between users on a dating site. Most of the edges (i.e. messages) are between men and women; there are fewer, but nonzero messages between men and men, and women and women. The graph would be mostly, but not completely bipartite, and the Laplacian spectra would be mostly, but not completely symmetric about 1.

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.

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.

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.