Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 12 more comments

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks. Do you have source for that statement? –  passerby51 Oct 5 '13 at 21:27
    
The first I found was hamilton.ie/skirkland/signless_bipartite_preprint.pdf; the result is much older than this source and is definitely folklore, –  Chris Godsil Oct 5 '13 at 22:26
    
Thanks for the link. That one looks interesting as they seem to have results for approximately bipartite graphs too. Any other such reference is also welcome. –  passerby51 Oct 6 '13 at 0:44
    
@passerby51 You might be interested in this as well: arxiv.org/abs/1307.7749 (does this count as a shameless plug?) –  Felix Goldberg Mar 16 at 21:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.