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

Question

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?

Answer 1

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} $$

Answer 2

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.

Answer 3

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.

Answer 4

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.