# How to calculate the number of automorphisms of a given graph?

How do determine the number of isomorphisms that a graph has to itself?

For instance, suppose we have the following graph:

How do I determine how many isomorphisms there are from G itself?

Here are all 48 automorphisms generated by Sage:

$$\begin{gathered} {\text{() }} \hfill \\ {\text{(d f)(e g)(h k) }} \hfill \\ {\text{(d e) }} \hfill \\ {\text{(a b) }} \hfill \\ {\text{(b m) }} \hfill \\ {\text{(f g) }} \hfill \\ {\text{(a m b) }} \hfill \\ {\text{(a b)(f g) }} \hfill \\ {\text{(a b)(d f)(e g)(h k) }} \hfill \\ {\text{(a b m) }} \hfill \\ {\text{(b m)(d e) }} \hfill \\ {\text{(d e)(f g) }} \hfill \\ {\text{(b m)(d f)(e g)(h k) }} \hfill \\ {\text{(d g e f)(h k) }} \hfill \\ {\text{(d f e g)(h k) }} \hfill \\ {\text{(b m)(f g) }} \hfill \\ {\text{(a b)(d e) }} \hfill \\ {\text{(d g)(e f)(h k) }} \hfill \\ {\text{(a m) }} \hfill \\ {\text{(a m b)(f g) }} \hfill \\ {\text{(b m)(d e)(f g) }} \hfill \\ {\text{(a m b)(d f)(e g)(h k) }} \hfill \\ {\text{(a b)(d f e g)(h k) }} \hfill \\ {\text{(a m b)(d e) }} \hfill \\ {\text{(a b m)(d f)(e g)(h k) }} \hfill \\ {\text{(b m)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d e) }} \hfill \\ {\text{(a b)(d e)(f g) }} \hfill \\ {\text{(b m)(d g e f)(h k) }} \hfill \\ {\text{(a b m)(f g) }} \hfill \\ {\text{(a b)(d g e f)(h k) }} \hfill \\ {\text{(a b m)(d g e f)(h k) }} \hfill \\ {\text{(a b)(d g)(e f)(h k) }} \hfill \\ {\text{(a m b)(d e)(f g) }} \hfill \\ {\text{(a m b)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d f e g)(h k) }} \hfill \\ {\text{(a m)(d f)(e g)(h k) }} \hfill \\ {\text{(a m)(d e) }} \hfill \\ {\text{(b m)(d g)(e f)(h k) }} \hfill \\ {\text{(a m b)(d g e f)(h k) }} \hfill \\ {\text{(a m)(f g) }} \hfill \\ {\text{(a b m)(d e)(f g) }} \hfill \\ {\text{(a m b)(d g)(e f)(h k) }} \hfill \\ {\text{(a m)(d e)(f g) }} \hfill \\ {\text{(a m)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d g)(e f)(h k) }} \hfill \\ {\text{(a m)(d g e f)(h k) }} \hfill \\ {\text{(a m)(d g)(e f)(h k)}} \hfill \\ \end{gathered}$$

Hopefully someone knows a better way of doing this, but it is actually possible just to count them.

How many places can c be mapped to? What about a, m and b? etc.

The orbit-stabiliser theorem (if you know it) makes this a bit easier. I would apply it to

one of d, e, f or g.

• I recently learned that your idea here can be used to show that counting $Aut(G)$ is in $P^{NP}$. The decision problem you need to solve is "is $x$ in the orbit of $y$ under $Aut$." Using this, you can count the size of the orbit of $x$. Then you color $x$ to get a new graph $G'$, whose automorphisms is the stabilizer of $x$. (You can "color" the node by adding a gadget.) By recursion you can count $Aut(G')$, and then you can compute $Aut(G)$ by the orbit stabilizer theorem. This was surprising to me, because a priori counting Aut(G) could be $\# P$-hard, but this shows that it is not. Oct 7, 2019 at 2:29

By hand is not easy. It can be done for small graphs like this. Notice the vertices that are "different" from the others. For example, any automorphism must fix $c$, because $c$ is the only vertex whose neighbors have degree $1$. $a$, $b$, and $m$ can be permuted freely, this gives automorphisms $(a \ b), (a \ m), (b \ m), (a \ b \ m), (a \ m \ b)$. You also have six vertices of degree $3$, how can they be permuted? How can they be distinguished from each other?

I count 48 automorphisms.

Considering the fact, that isomorphic graph $H$ differs from the an initial graph $G$ by a permutation of columns of adjacency matrix, we can possibly have $n!$ of such permutations, where $n$ is a number of vertices of both graphs.

• This isn't actually helpful. The graph in question doesn't have $10!$ automorphisms; it has only 48, and yhe question is how to find that out. Your answer doesn't give Alex Wong any hint of an answer.
– MJD
Oct 9, 2014 at 1:07