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

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!

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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 '12 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 '12 at 14:46

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.