8 Automorphism groups and isomorphism testing for graphs

The first version of this function returns the automorphism group of the (directed) graph gamma, using nauty (this can also be accomplished by typing AutomorphismGroup(gamma)). The automorphism group \Aut(gamma ) of gamma is the group consisting of the permutations of the vertices of gamma which preserve the edge-set of gamma.

In the second version, colourclasses is an ordered partition of the vertices of gamma (into colour-classes), and the subgroup of \Aut(gamma ) preserving this ordered partition is returned. The ordered partition should be given as a list of sets, although the last set in the list may be omitted. Note that we do not require that adjacent vertices be in different colour-classes.

gap> gamma := JohnsonGraph(4,2);                   
rec( isGraph := true, order := 6, 
  group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]), 
  schreierVector := [ -1, 2, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5 ] ], 
  representatives := [ 1 ], 
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], 
  isSimple := true )
gap> Size(AutGroupGraph(gamma)); 
48
gap> Size(AutGroupGraph(gamma,[[1,2,3],[4,5,6]])); 
6
gap> Size(AutGroupGraph(gamma,[[1,6]]));          
16

8.2 IsIsomorphicGraph

This boolean function uses the nauty package to test whether graphs gamma1 and gamma2 are isomorphic. The value true is returned if and only if the graphs are isomorphic (as directed, uncoloured graphs).

The optional boolean parameter firstunbindcanon determines whether or not the canonicalLabelling components of both gamma1 and gamma2 are first unbound before testing isomorphism. If firstunbindcanon is true (the default, safe and possibly slower option) then these components are first unbound. If firstunbindcanon is false, then any existing canonical labelling is used, which was the behaviour in versions of GRAPE before 4.0. However, since canonical labellings can depend on the version of nauty (currently 2.0b5), certain parameters of nauty (always set the same for a given graph by GRAPE 4.1), and the compiler and computer used, you must be sure that if firstunbindcanon=false then the canonicalLabelling component(s) which may already exist for gamma1 or gamma2 were created in exactly the same environment in which you are presently computing. We remark that GRAPE 4.1 now sets nauty parameters differently than before for non-simple graphs (and so canonical labellings may be different than before), in order to avoid a performance problem with certain sparse directed graphs.

gap> gamma := JohnsonGraph(7,4);;
gap> delta := JohnsonGraph(7,3);;
gap> IsIsomorphicGraph( gamma, delta );
true 

[Up] [Previous] [Next] [Index]