Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? - MathOverflow

Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?

2012-02-21T11:39:54Z

It is well known that

1) if there exists a non-trivial automorphism of a graph $G$ with corresponding permutation matrix $P$ then if $(v,\lambda)$ is an eigenvector-eigenvalue pair of the graph Laplacian $L(G)$ then $(Pv,\lambda)$ is also an eigenvector-eigenvalue pair (if $v$ and $Pv$ are linearly independent then this gives rise to eigenvalues with multiplicity greater than 1) and,

2) if all the eigenvalues of the $L(G)$ are simple than every automorphism of G has order 1 or 2.

If $G$ exhibits only a trivial automorphism ($G$ is asymmetric) can it be said that $L(G)$ has no repeated eigenvalues?

If not, a counterexample would be most helpful. I haven't found one on a brute force check of all graphs up to 9 nodes.

(I am assuming unweighted, undirected graphs)

Answer by gordon-royle for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?

2012-02-21T12:21:32Z

This is false.

There are strongly regular graphs with trivial automorphism group; these will have many repeated eigenvalues (both for adjacency matrix and Laplacian).

You can find some examples in the answers to this question:

http://mathoverflow.net/questions/41194/are-almost-all-strongly-regular-graphs-rigid

Answer by Louigi Addario-Berry for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?

2012-02-21T15:04:11Z

Take two asymmetric $d$-regular graphs $H_1,H_2$, and let $G$ be their disjoint union. Then $d$ will be a repeated eigenvalue.

If you want $G$ connected, take the complement of the graph obtained by the above construction. Graph complements preserve asymmetry and repeated eigenvalues.