How to use spectral graph theory to get a measure for graph symmetry? I looked at graphs, like $K_{12}$ or Frucht's graph and wondered if their spectrum, more specific the degenercies of their eigenvalues, is a mesaure for the (a)symmetry of the corresponding graph?
For the examples given it works out quite nice:
$$
\begin{eqnarray}
\text{Graph} && \text{Spectrum (approximated)}\\
\hline
K_{12} && (-1)^{11}11^1\\
\text{Frucht} && (-2.33)^1 (-2)^1 (-1.80)^1 (-1.45)^1 (-1)^1 (-0.44)^1 \\
&&0^1\\&& 0.51^1 1.24^1 2^1 2.27^1 3^1
\end{eqnarray}
$$
The asymmetric cubic graph of Frucht is an identity graph, i.e. the graph automorphism group contains only the identity, and also shows lowest symmetry in its eigenvalues.

A graph can have a small number of eigenvalues, yet no symmetries.  For example, strongly regular graphs have exactly 3 eigenvalues, but it is conjectured that almost all SRGs have trivial automorphism group.
This paper gives an upper bound on the size of the automorphism group of an SRG.
