[GAP Forum] Isomorphism Classes of a Graph

[Dima Pasechnik]

On Thu, May 29, 2014 at 09:03:44AM +0000, Wolstenholme, Robert wrote:
> Is there a function in GAP/Grape that will return all isomorphism
> classes of a graph with N vertices (i.e. a single element from each
> class)?
> 
> The function GraphIsomorphismRepresentatives
> (http://www.maths.qmul.ac.uk/~leonard/grape/manual/CHAP008.htm#SECT005)
> looks to be a candidate but it seems I may be having to input a very
> large list to get my desired result.
> 
> I can see a potential inductive type method where if we know all
> isomorphism classes with k edges in total we only have to consider
> additional edges added to the graphs representing these classes to
> find the isomorphism classes with k+1 edges in total. Has anyone
> seen anything that has already been coded.


If you don't mind using C programs (included within Grape, although
not really interfaced with GAP) you can use  geng, a C program which
is a part of nauty by B.McKay. 
The advantage is that it is much faster than anything coded in GAP
langauge for this purpose.

It should not be too hard to import the output of geng into GAP/Grape.

There are also ready to use databases of isomorphism classes of graphs
on small number of vertices available, e.g. in Sage:
http://sagemath.org/doc/reference/graphs/sage/graphs/graph_database.html

HTH,
Dmitrii