1
$\begingroup$

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!

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2012 at 13:54
  • $\begingroup$ @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. $\endgroup$ Jun 26, 2012 at 14:46

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.