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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 16, 2014 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .