7
$\begingroup$

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

For instance, suppose we have the following graph:

Graph G

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

$\endgroup$

4 Answers 4

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Elle Najt
    Oct 7, 2019 at 2:29
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – MJD
    Oct 9, 2014 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.