3
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • $\begingroup$ 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] $\endgroup$
    – joro
    Oct 5, 2013 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Oct 5, 2013 at 14:17
  • $\begingroup$ @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. $\endgroup$
    – passerby51
    Oct 5, 2013 at 14:17
  • $\begingroup$ @ 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. $\endgroup$
    – passerby51
    Oct 5, 2013 at 14:19
  • $\begingroup$ What are the eigenvalues of K_{2,2} and K_{3,3} with your definition to test my implementation? $\endgroup$
    – joro
    Oct 5, 2013 at 14:37

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. Do you have source for that statement? $\endgroup$
    – passerby51
    Oct 5, 2013 at 21:27
  • $\begingroup$ The first I found was hamilton.ie/skirkland/signless_bipartite_preprint.pdf; the result is much older than this source and is definitely folklore, $\endgroup$
    – Chris Godsil
    Oct 5, 2013 at 22:26
  • $\begingroup$ 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. $\endgroup$
    – passerby51
    Oct 6, 2013 at 0:44
  • $\begingroup$ @passerby51 You might be interested in this as well: arxiv.org/abs/1307.7749 (does this count as a shameless plug?) $\endgroup$
    – Felix Goldberg
    Mar 16, 2014 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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