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!
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Jun 26, 2012 at 12:49
-
$\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$ Commented 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$ Commented Jun 26, 2012 at 14:46