Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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