Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:19:04Z http://mathoverflow.net/feeds/question/89096 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89096/does-graph-asymmetry-imply-all-eigenvalues-of-the-graph-laplacian-are-simple Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? unknown (yahoo) 2012-02-21T11:39:54Z 2012-02-21T15:04:11Z <p>It is well known that</p> <p>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, </p> <p>2) if all the eigenvalues of the $L(G)$ are simple than every automorphism of G has order 1 or 2. </p> <p>If $G$ exhibits only a trivial automorphism ($G$ is asymmetric) can it be said that $L(G)$ has no repeated eigenvalues?</p> <p>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.</p> <p>(I am assuming unweighted, undirected graphs)</p> http://mathoverflow.net/questions/89096/does-graph-asymmetry-imply-all-eigenvalues-of-the-graph-laplacian-are-simple/89099#89099 Answer by gordon-royle for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? gordon-royle 2012-02-21T12:21:32Z 2012-02-21T12:21:32Z <p>This is false.</p> <p>There are strongly regular graphs with trivial automorphism group; these will have many repeated eigenvalues (both for adjacency matrix and Laplacian).</p> <p>You can find some examples in the answers to this question:</p> <p><a href="http://mathoverflow.net/questions/41194/are-almost-all-strongly-regular-graphs-rigid" rel="nofollow">http://mathoverflow.net/questions/41194/are-almost-all-strongly-regular-graphs-rigid</a></p> http://mathoverflow.net/questions/89096/does-graph-asymmetry-imply-all-eigenvalues-of-the-graph-laplacian-are-simple/89113#89113 Answer by Louigi Addario-Berry for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? Louigi Addario-Berry 2012-02-21T15:04:11Z 2012-02-21T15:04:11Z <p>Take two asymmetric $d$-regular graphs $H_1,H_2$, and let $G$ be their disjoint union. Then $d$ will be a repeated eigenvalue. </p> <p>If you want $G$ connected, take the complement of the graph obtained by the above construction. Graph complements preserve asymmetry and repeated eigenvalues. </p>