Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.