1

If the eigenvalues of the Laplacian matrix of a graph G are all simple, is it always the case that the eigenvalues of the adjacency matrix of G are all simple as well?

Thanks in advance!

flag

1 Answer

4

According to my calculations in sage, 13 of the 156 graphs on six vertices have simple Laplacian eigenvalues but repeated adjacency eigenvalues. The first of the 13 is a tree with adjacency matrix: $$ \left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{array}\right) $$ There are no examples on less than six vertices.

Note that if $M$ is symmetric and $D$ is diagonal, there is essentially no relation between the eigenvalues of $M$ and the eigenvalues of $M+D$ and so it would be very surprising if there was a relation of the sort you asked for.

link|flag
Thank you. I had already found a graph with the spectrum of its adjacency matrix consisting entirely of simple eigenvalues, but whose Laplacian spectrum not entirely consisting of simple eigenvalues, which is why I did not ask the reverse question as well. The example I found happens to have 6 vertices as well. – Alexander Farrugia Jun 26 at 13:54
@Alexander Farrugia: I found 18 graphs on six vertices with simple adjacency eigenvalues and repeated Laplacian eigenvalues. There may be examples on fewer than six vertices, I didn't check. – Chris Godsil Jun 26 at 14:46

Your Answer

Get an OpenID
or

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