1
$\begingroup$

It is a well known fact that there are non-isomorphic connected graphs whose adjacency matrix have the same spectrum.

This has been discussed, for example, in this older post.

However, in the examples given, the graph spectrum always some has repeated eigenvalues. Are there examples where this is not the case, but rather each eigenvalue is unique?

On a different but related problem: Is it true that if two graphs have only single eigenvalues (multiplicity 1) in their spectrum, then it is easy to determine if they are isomorphic or not?

$\endgroup$
0
$\begingroup$

The following two graphs both have characteristic polynomial $$\det(x I - A_G) =x (x + 1) (x^2 - 2) (x^3 - x^2 - 5x + 1)$$ which has no repeated roots:

enter image description here

This was found by the basically-brute-force way of examining all $7$-vertex graphs returned by Mathematica's GraphData command, which actually found $26$ cospectral pairs with no repeated eigenvalues.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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