# Number of isomorphic graphs for a particular digraph

Suppose we have a simple digraph $G$ with $g$ vertices and $a$ arcs. How should one count all graphs in that isomorphism class (i.e., all graphs isomorphic to graph $G$).

Any pointers would be really appreciated.

-

## 1 Answer

Are you looking for the number of labeled digraphs isomorphic to a given unlabeled one?

So really you are looking for the set of permutations of the labels which result in distinct labellings. E.g. for the directed claw $a\rightarrow b$, $a\rightarrow c$, $a\rightarrow d$, any permutation of the labels $b,c,d$ give the same labeled digraph, and any digraph with a different root of the claw with be nonisomorphic. In this example it seems that there are only 4 distinct labeled digraphs.

If this is the case, then this is equivalent to finding the order of the isomorphism group of graph. There is lots of research on both algorithms for this and its computational complexity (it's a subclass of graph isomorphism).

Practically, the go-to implementation (that is the implementation that you really should 'go to' for practical purposes) is nauty.

-
thanks for reply! If I understand correctly, I need to calculate the number of automorphisms of the input graph? –  Andrej Apr 12 '11 at 10:19
@Andrej: Yes, that is correct. Another (equally valid) way to say it is that you want to compute the order of the automorphism group of the graph. –  Mitch Apr 12 '11 at 12:34