How to use spectral graph theory to get a measure for graph symmetry?

204 Views Asked by At

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.

2

There are 2 best solutions below

2
On BEST ANSWER

Basically, having a large automorphism group tends to push the multiplicities up. There is an old result that the eigenvalues of a vertex-transitive graph cannot all be simple. Each eigenspace of the graph provides a representation of the automorphism group, and so if the group has no faithful representation of low degree the multiplicities go up.

To view it another way, the permutation matrices in the automorphism group lie in the algebra of matrices that commute with the adjacency matrix $A$, and the dimension of this is the sum of the squares of its eigenvalue multiplicities.

As Randy E notes the converse is not true, we can have large multiplicities and trivial group.

1
On

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.