Cospectral graphs that are non-isomorphic and that only have simple eigenvalues

Question

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?

Answer 1

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:

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.

Answer 2

Yes, it is easy to determine if they are isomorphic or not as long as they are cospectral and have distinct eigenvalues (multiplicity 1).

But you cannot directly say that they are isomorphic. As Misha gave an example which has same distinct eigenvalues but they are not isomorphic.

Let $A,B$ are adjacency or laplacian of two graphs that you want to test. Their eigendecompositions are $A=U \Sigma U^{T}$ and $B=V \Sigma V^{T}$. See their eigenvalues ($\Sigma$ is a diagonal matrix which keeps eigenvalues) are the same and let's suppose it has distinct values. $S$ is a diagonal matrix that includes $\mp1$ and $P$ is a permutation matrix where each column and row there is single 1 and rest of them 0.

If you find $P$ and $S$ matrices that meets $PU=VS$ then they are isomorphic, unless they are not.

If some eigenvalues are repeated in $\Sigma$, even though you find $P$ and $S$ matrix that meets $PU=VS$, still you cannot say they are isomorphic.