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)


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:

Are "almost all" strongly regular graphs rigid?


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.


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.