MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
up vote 10 down vote accepted

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?

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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