Return to Revisions

Corollary 2.7 of Norman Biggs's book Algebraic Graph Theory says that if $d$ is the diameter of the graph, then it has at least $d+1$ distinct 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.