Return to Revisions

For a regular graph, eigenvalues and Laplacian eigenvalues coincide. I believe that in Fan Chung's book Spectral Graph Theory it is proved that if $d$ is the diameter of the graph, then it has at least $d+1$ distinct Laplacian eigenvalues. (This bound is tight, and is achieved for example by distance-regular graphs.) So in particular, having a lot of repeated eigenvalues does not necessarily indicate a lot of automorphisms; it might just mean that the diameter is small. For example, a strongly regular graph has only three distinct eigenvalues but often has trivial automorphism group.