3
$\begingroup$

Given a small graph, how can you manually calculate the number of automorphisms? I thought of seeing the number of nodes of a particular degree and permuting among them, but aren't there other factors to consider, like the node being part of a cycle, etc? For example, this graph:

enter image description here

Suppose b had two more edges going to two different nodes, then you can't map b to g, even though they have the same degree. So how do you do this?

  • 0
    Ah ... thanks for the link2012-10-15

1 Answers 1

6

It is in general not even simple to check if two graphs are isomorphic. In your case, we see that $a,b,m$ are the only degree 1 nodes, hence any automorphism must permute them. Next $c$ is characterized by being the only node with degree 1 neighbours, hence $c$ must be a fixed point (which at the same instant shows that $a,b,m$ may be permuted arbitrarily). You may then note that $d$ can be mapped to any of $d,e,f,g$, but then $e$ must be mapped to the common neighbour of $\phi(d)$ and $\phi(c)=c$. Finally you can map $f$ to any of the remaining neighbours of $c$ and the rest, i.e. the images of $g, h, k$ are then determined. We conclude that the automorphism gorup is isomorphic to $S_3\times D_4$.