[Nauty] size of isomorph groups

Daniele Degiorgi degiorgi at hispeed.ch
Sat May 28 15:20:01 EST 2005

It could be that you did a little confusion between different notions.

Two graphs are isomorphic if there is a mapping between the vertices
preserving adjacency. An isomorph group could contain all isomorphic graphs,
but this is very unlikely to be an algebraic group as there is at least
apparently no operation defined and its size is almost surely infinite. Thus
even if one could define it, it is very unlikely useful.

Instead in graph theory there exists an automorphism group, that contain
permutations (and not graphs) and the permutation itself is the algebraic
operation of the group. And for each graph its automorphism group is a
subgroup of the symmetric group (if you are unfamiliar with these concepts
you should consult a good text in algebra) and contains all possible
permutations of the vertices that preserve the adjacency.

Nauty computes as grpsize precisely the size of the automorphism group.

It is a obviously a necessary condition for two isomorphic graphs to have
the same automorphism group, but this condition is not sufficient, as for
example a graph and its complement have obviously the same automorphism

I hope that this helps.


-----Original Message-----
From: nauty-list-admin at cs.anu.edu.au [mailto:nauty-list-admin at cs.anu.edu.au]
On Behalf Of Radics Geza
Sent: venerdì, 27. maggio 2005 01:38
To: nauty-list at cs.anu.edu.au
Subject: [Nauty] size of isomorph groups


I'm a newbee, I read the documentation, but I cant figure out, that 
nauty could be say to me
what is the size of the isomorph groups, how many graphs are in the groups?
Somebody can help me, how can I do it?

This is the nauty mailing list
Post messages to nauty-list at cs.anu.edu.au
nauty page: http://cs.anu.edu.au/~bdm/nauty/
list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list

More information about the Nauty mailing list