# When does graph Laplacian have eigenvalue -1?

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.

-
According to sage $K_{2,2}$ has eigenvalues of the Laplacian: [4, 0, 2, 2] and $K_{3,3}$: [6, 0, 3, 3, 3, 3] –  joro Oct 5 '13 at 14:10
The definition you are using of the graph laplacian is different / "wrong" --- it is either $D-A$, or the normalized version $I-D^{-1/2}AD^{-1/2}$. The Graph Laplacian is a well-known semidefinite matrix, whose smallest eigenvalue is $0$---so it can never have $-1$ as an eigenvalue. –  Suvrit Oct 5 '13 at 14:17
@joro, There are many definitions of the Laplacian. The one I have mentioned in my post is a bit non-standard. (It is related to the symmetric Laplacian sometimes defined as $I - D^{-1/2} A D^{-1/2}$.) For the Laplacian that I defined, I still think what I wrote is correct. –  passerby51 Oct 5 '13 at 14:17
@ suv....rit, A definition can't be wrong (it can be nonstandard). I am defining the Laplacian the way I mentioned above. You can rename it to whatever you like if you don't like the name. By the way, the eigenvalues of $I - D^{-1/2} A D^{-1/2}$ and $D^{-1/2} A D^{-1/2}$ are very closely related (by an affine transform $x \mapsto -x+1$). You can reformulate my question in terms of that matrix. –  passerby51 Oct 5 '13 at 14:19
What are the eigenvalues of K_{2,2} and K_{3,3} with your definition to test my implementation? –  joro Oct 5 '13 at 14:37

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.)