# 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, 2013 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. Oct 5, 2013 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. Oct 5, 2013 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. Oct 5, 2013 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, 2013 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.)