Consider an undirected graph $G$ with (symmetric) adjacency matrix $A \in \{0,1\}^{n \times n}$ and degree sequence $d = (d\_i)$ where $d\_i = \sum\_{j} A\_{ij}$. Assume that every node has degree at least $1$. Let $D = \text{diag}(d)$ be the diagonal matrix with the degrees $(d\_i)$ on its diagonal. Define the Laplacian of the graph to be $L = D^{-1/2} A D^{-1/2}$.


It is not hard to see that $\sqrt{d} := (\sqrt{d\_i})$ is an eigenvector associated with eigenvalue $1$. By Perron-Frobenius theory, it seems that $1$ is the Perron root (since its eigenvector has strictly positive entries), from which it follows that the spectral radius of $L$ is $1$, that is, for any eigenvalue $\lambda$ of $L$, we have $|\lambda| \le 1$.


The question is:


* For what graphs, $L$ will have an eigenvalue $-1$?


It seems to me that this question is related to graph-colorings. If we can color the nodes of the graph with $\{+,-\}$, so that adjacent nodes have different colors, then $(\pm\sqrt{d\_i})$ is an eigenvector with eigenvalue $-1$. Since $2$-colorable graphs are exactly the bipartite graphs, it seems that a sufficient condition is being bipartite. But is this necessary?


EDIT: Please note that the Laplacian I defined above is a bit nonstandard. I am talking about the eigenvalues of $L$, whatever name you want to attach to it. (This version is actually quite standard among the people that use the Laplacian for spectral clustering.) If you think a Laplacian should be defined as $\widetilde{L} = I - D^{-1/2}A D^{-1/2}$, then please read my question as, "When does the Laplacian $\widetilde{L}$ has eigenvalue $2$"?


EDIT2: The conjecture is not true as I wrote if the graph is disconnected, since it could have a connected component that is bipartite, and many that are not. The bipartite component will contribute a $-1$ eigenvalue. So, let us add the assumption that the graph is connected.



When does graph Laplacian have eigenvalue -1?
We have $\det(tI-L) =\det(D^{-1}(tD-A))$. The matrix $D-A$ is positive semidefinite; it is the usual Laplacian in graph theory. The matrix $A+D$ is also positive semidefinite, and if the underlying graph $G$ has $n$ vertices
and exactly $b$ components are bipartite, its rank is $n-b$. Hence $-1$ is an eigenvalue of $L$ if and only if some component of $G$ is bipartite. (The matrix $A+D$ is often called the unsigned Laplacian.)


