Automorphism Group of a Graph or Digraph

The automorphism group functionality is an implementation of B. McKay's nauty programme. For a paper describing nauty see [McK81]. There also exists a user's manual [McK] describing nauty's essential features.

Subsections

• The Automorphism Group Function
• nauty Invariants
• Graph Colouring and Parameter Setting: A General Discussion
• Variants of Automorphism Group
• Action of Automorphisms

The Automorphism Group Function

AutomorphismGroup( G: parameters) : Grph -> GrpPerm, GSet, GSet, PowMap, Map, Grph

Compute the automorphism group of the graph G. This returns the group A, the vertex and edge G--sets (in that order), the power structure (A) of all automorphisms of G, and the transfer map from A to (A). Note that G may be directed or undirected. For small graphs (i.e. having less than 500 vertices) the canonically labelled graph is also returned.

The automorphism group computation may be driven by several user parameters. There are four principal parameters: Canonical, Stabilizer, Invariant and Print. Some of these parameters have associated parameters.

     Canonical: BoolElt                  Default: {false}

If the parameter Canonical is set true, then the canonically labelled graph will be returned. If the graph has fewer than 500 vertices then the default value for this parameter is true, while if the graph has 500 or more vertices, the default value is false.

     Stabilizer: [ { GrphVert } ]        Default: 

If the parameter Stabilizer is assigned a partition P of the vertex--set of G as its value, then the subgroup of the automorphism group of G that preserves the partition P will be computed. The partition given as Stabilizer need not be a partition of the full vertex set of G. Any vertices not covered by the sets in Stabilizer are assumed to belong to an extra partition cell.

     Invariant: MonStgElt                Default: 

Use the named invariant to assist the auto group computation. The invariant is specified by a string which is the name of a C function computing an invariant, as on page 14 of the nauty manual [McK]. The default value for Invariant is "Null" when G is an undirected graph, or "adjacencies" when G is a digraph. For a more detailed discussion on invariants see Subsection nauty Invariants.

There are three optional associated parameters to Invariant:

     Minlevel: RngIntElt                 Default: 0

     Maxlevel: RngIntElt                 Default: 

     Arg: RngIntElt                      Default: 

An expression, depending upon the type of invariant. When G is undirected these three parameters take the values 0, 1, and 0 respectively. When G is a digraph they take the values 0, 2, and 0 respectively. When Invariant is one of "indsets", "cliques", "cellcliq", or "cellind", the default value for Arg is 3. Again, see Subsection nauty Invariants for more information.

     Print: RngIntElt                    Default: 0

The integer valued parameter Print is used to control informative printing according to the following table:

Print := 0 : No output (default).

Print := 1 : Statistics are printed.

Print := 2 : Summary upon completion of each level.

Print := 3 : Print the automorphisms as they are discovered.

     IgnoreLabels: BoolElt               Default: false

By default, the automorphism group computation respects vertex labels (colours). That is, elements of the group will only take a vertex to an identically labelled vertex. The Boolean value IgnoreLabels will treat all vertices as identically labelled for the purposes of this computation.

nauty Invariants

Invariants can be used to supplement the built--in partition refinement code in nauty, to assist in the processing of difficult graphs. Invariants are used with three parameters:

Minlevel: the minimum depth in the search tree at which an invariant is to be applied (default 0)

Maxlevel: the maximum depth in the search tree at which an invariant is to be applied (default 1 for undirected graphs and 2 for digraphs)

Arg: an integer argument which has a different meaning (or no meaning) for each invariant

The root of the tree, corresponding to the partition provided by the user, has level 1. Note that the invariants use an existing partition and attempt to refine it. Thus, it can be that an invariant fails to refine the partition at the root of the search tree but succeeds further down the tree. In particular, all invariants necessarily fail at the root of the tree if the graph is vertex-transitive.

The invariants are :

• "default"

• "twopaths"

• "adjtriang"

• "triples"

• "quadruples"

• "celltrips"

• "cellquads"

• "cellquins"

• "cellfano",
• "cellfano2"

• "distances"

• "indsets"

• "cliques"

• "cellind"

• "cellcliq"

• "adjacencies"

These invariants are further described on page 14 of the nauty manual [McK]. Also, we provide a facility enabling users to test if a specific Invariant achieves a partition refinement for a graph G.

TestNautyInvariant(G: parameters) : Grph -> BoolElt

Returns true if and only the invariant in Invariant could refine G's vertex--set partition. If no invariant is set in Invariant then the refinement procedure which is tested is taken to be the default one.

Four parameters can be passed:

     Stabilizer: [ { Vert } ]            Default: 

     Invariant: MonStgElt                Default: 

     Arg: RngIntElt                      Default: 

     IgnoreLabels: BoolElt               Default: false

The parameters have the same meaning as for AutomorphismGroup.

Graph Colouring and Parameter Setting: A General Discussion

For any calls to nauty via magma functions the graph colouring of a graph G (as set by AssignLabels or a similar function) is taken as an intrinsic property of G. Consequently, the default automorphism group computed by nauty is the group for the coloured graph G. In particular this implies that, when G is coloured, this default automorphism group is not G's full automorphism group.

There are several magma functions which make use of the automorphism group of a graph, and therefore rely on a call to nauty. We list them here:

1. IsDistanceRegular, GirthCycle, Girth

2. IsDistanceTransitive, IsTransitive, IsPrimitive, IsSymmetric

3. IsEdgeTransitive

4. EdgeGroup, OrbitsPartition, IsIsomorphic, CanonicalGraph

The functions in Group 1 make use of the automorphism group of the graph only as a means to improve efficiency. If no group has been computed yet for the graph under consideration then the full group is computed. This does not require any user--supplied parameters.

The functions in Group 2 need the full automorphism group of the graph G. As seen above, the full group for G is computed only if G does not possess a colouring. Consequently, if G has a colouring, all the functions in Group 2 will return false. These functions accept user--supplied parameters allowing to disable the graph colouring.

The function in Group 3 needs the default automorphism group of G (thus G may be coloured). This function also accepts user--supplied parameters allowing to disable the graph colouring.

The functions in Group 4 use the default automorphism group. This group may be modified by user--supplied parameters (for example by setting a Stabilizer).

For the functions in Group 1 where no user--supplied parameters are accepted it is still possible to drive the group computation by setting an appropriate Invariant parameter. This is achieved by first computing the group using AutomorphismGroup while setting Invariant. This parameter is then remembered for any further (re)computation of the default (or full) automorphism group.

The parameter suite for any of the functions in Group 2, 3, or 4 allows users to set the Invariant as well. As a rule, if none is supplied, and if another Invariant was set and used for an earlier computation of the automorphism group of G then the latter is taken to be the default invariant. To revert to the default invariant it is then sufficient to set Invariant to "default".

Variants of Automorphism Group

CanonicalGraph(G : parameters ) : Grph -> Grph

Given a graph G, return the canonically labelled graph isomorphic to G. The parameters are almost identical to those for AutomorphismGroup (with the exception of Canonical which is irrelevant here and of the printing facilities).

EdgeGroup(G : parameters ) : Grph -> GrpPerm, GSet

Returns the automorphism group of the graph G in its action on the edges of G, and the G--set of edges of G. The parameters are almost identical to those for AutomorphismGroup (with the exception of Canonical and the printing facilities).

IsIsomorphic(G, H : parameters ) : GrphDir, GrphDir -> BoolElt, Map

IsIsomorphic(G, H : parameters ) : GrphUnd, GrphUnd -> BoolElt, Map

This function returns true if the graphs G and H are isomorphic. If G and H are isomorphic, a second value is returned, namely a mapping between the vertices of G and the vertices of H giving the isomorphism.

The parameters accepted by IsIsomorphic are almost the same as for AutomorphismGroup. The exceptions are:

     Stabilizer: [ { Vert } ]            Default: 

This sets the stabilizer set for both graphs G and H. If one wishes to set two distinct stabilizers then one would also use:

     Stabilizer2: [ { Vert } ]           Default: 

This sets the stabilizer set for the second graph H only.

     IgnoreLabels: BoolElt               Default: false

This indicates whether or not to ignore the graph labelling for both graphs G and H.

Graph isomorphism is understood as mapping colours to colours and stabilizers to stabilizers. Consequently comparing two graphs for isomorphism will always return false if one graph is coloured while the other one is not. Similarly two graphs can't be isomorphic if each is coloured using a different set of colours. Moreover, it is a nauty requirement that in order to achieve mapping of stabilizers they must be compatible: that is, they must have same-sized cells in the same order.

Example Graph_AutomorphismGroup (H93E14)

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
>  
> AssignLabels(VertexSet(G), ["a", "b", "a", "b", "b"]);
> A, _, _, _, _, C1 := AutomorphismGroup(G);
> A;
Permutation group A acting on a set of cardinality 5
Order = 2
  (1, 3)(4, 5)
> C1;
Graph
Vertex  Neighbours

1       3 5 ;
2       4 5 ;
3       1 4 ;
4       2 3 ;
5       1 2 ;

> B, _, _, _, _, C2 := AutomorphismGroup(G : IgnoreLabels := true);
> B;
Permutation group B acting on a set of cardinality 5
Order = 10 = 2 * 5
  (2, 5)(3, 4)
  (1, 2)(3, 5)
> C2;
Graph
Vertex  Neighbours

1       2 3 ;
2       1 4 ;
3       1 5 ;
4       2 5 ;
5       3 4 ;

> C, _, _, _, _, C3 := AutomorphismGroup(G : Stabilizer :=
> [ { VertexSet(G) | 1, 2 } ]);
> C;
Permutation group C acting on a set of cardinality 5
> #C;
1
> C3;
Graph
Vertex  Neighbours

1       3 4 ;
2       3 5 ;
3       1 2 ;
4       1 5 ;
5       2 4 ;

Example Graph_GraphIsomorphim (H93E15)

> G1 := CompleteGraph(5);
> AssignLabels(VertexSet(G1), ["a", "a", "b", "b", "b"]);
> G2 := CompleteGraph(5);
> IsIsomorphic(G1, G2);
false
> IsIsomorphic(G1, G2 : IgnoreLabels := true);
true
> 
> V1 := Vertices(G1);
> V2 := Vertices(G2);
> S1 := { V1 | 1, 2, 3};
> S2 := { V2 | 3, 4, 5};
>
> IsIsomorphic(G1, G2 : Stabilizer := [S1],
>       Stabilizer2 := [S2]);
false
> IsIsomorphic(G1, G2 : Stabilizer := [S1],
>       Stabilizer2 := [S2], IgnoreLabels := true);
true
> IsIsomorphic(G1, G2 : Stabilizer := [S1],
> IgnoreLabels := true);
true
>
> SS1 := [ { V1 | 1}, {V1 | 2, 3} ];
> SS2 := [ { V2 | 3, 4}, { V2 | 1} ];
> IsIsomorphic(G1, G2 : Stabilizer := SS1, Stabilizer2 := SS2,
> IgnoreLabels := true);
false
> 
> SS1 := [ {V1 | 2, 3}, { V1 | 1} ];
> IsIsomorphic(G1, G2 : Stabilizer := SS1, Stabilizer2 := SS2,
> IgnoreLabels := true);
true

> G1 := CompleteGraph(5);
> AssignLabels(VertexSet(G1), ["a", "a", "b", "b", "b"]);
> G2 := CompleteGraph(5);
> IsIsomorphic(G1, G2);
false
> IsIsomorphic(G1, G2 : IgnoreLabels := true);
true
> G1 := CompleteGraph(5);
> G2 := CompleteGraph(5);
> AssignLabels(VertexSet(G1), ["a", "a", "b", "b", "b"]);
> AssignLabels(VertexSet(G2), ["a", "b", "a", "b", "a"]);
> IsIsomorphic(G1, G2);
false
> AssignLabels(VertexSet(G2), ["b", "a", "b", "a", "b"]);
> IsIsomorphic(G1, G2);
true
> 
> AssignLabels(VertexSet(G2), ["b", "c", "b", "c", "c"]);
> IsIsomorphic(G1, G2);
false
> 
> IsIsomorphic(G1, G2 : IgnoreLabels := true);
true

Action of Automorphisms

The automorphism group A of a graph G is given in its action on the standard support and it does not act directly on G. The action of A on G is obtained using the G--set mechanism. The two basic G--sets associated with the graph correspond to the action of A on the set of vertices V and the set of edges V of G. These two G--sets are given as return values of the function AutomorphismGroup or may be constructed directly. Additional G--sets associated with a graph may be built using the G--set constructors. Given a G--set Y for A, the action of A on Y may be studied using the permutation group functions that allow a G--set as a argument In this section, only a few of the available functions are described: see the section on G--sets for a complete list.

Image(a, Y, y) : GrpPermElt, GSet, Elt -> Elt

Let a be an element of the automorphism group A for the graph G and let Y be a G--set for A. Given an element y belonging either to Y or to a G--set derived from Y, find the image of y under a.

Orbit(A, Y, y) : GrpPerm, GSet, Elt -> GSet

Let A be a subgroup of the automorphism group for the graph G and let Y be a G--set for A. Given an element y belonging either to Y or to a G--set derived from Y, construct the orbit of y under A.

Orbits(A, Y) : GrpPerm, GSet -> [ GSet ]

Let A be a subgroup of the automorphism group for the graph G and let Y be a G--set for G. This function constructs the orbits of the action of A on Y.

Stabilizer(A, Y, y) : GrpPerm, Elt -> GrpPerm

Let A be a subgroup of the automorphism group for the graph G and let Y be a G--set for A. Given an element y belonging either to Y or to a G--set derived from Y, construct the stabilizer of y in A.

Action(A, Y) : GrpPerm, GSet -> Hom(Grp), GrpPerm, GrpPerm

Given a subgroup A of the automorphism group of the graph G, and a G--set Y for A, construct the homomorphism phi: A -> L, where the permutation group L gives the action of A on the set Y. The function returns:

• The natural homomorphism phi: A -> L;
• The induced group L;
• The kernel of the action (a subgroup of A).

ActionImage(A, Y) : GrpPerm, GSet -> GrpPerm

Given a subgroup G of the automorphism group of the graph structure G, and a G--set Y for A, construct the permutation group L giving the action of A on the set Y.

ActionKernel(A, Y) : GrpPerm, GSet -> GrpPerm

Given a subgroup A of the automorphism group of the graph G, and a G--set Y for A, construct the kernel of the action of A on the set Y.

Example Graph_AutomorphismAction (H93E16)

> S := { 1 .. 5 };
> V := &join[ Subsets({1..5}, 2*k) : k in [0..#S div 2]];
> E := { {u,v} : u,v in V | #(u sdiff v) eq 4 };
> G, V, E := StandardGraph( Graph< V | E >);
> G;                                                                   
Graph
Vertex  Neighbours

1       4 6 8 10 12 ;
2       5 6 9 12 14 ;
3       9 10 12 13 16 ;
4       1 7 9 14 16 ;
5       2 7 8 10 16 ;
6       1 2 13 15 16 ;
7       4 5 12 13 15 ;
8       1 5 9 11 13 ;
9       2 3 4 8 15 ;
10      1 3 5 14 15 ;
11      8 12 14 15 16 ;
12      1 2 3 7 11 ;
13      3 6 7 8 14 ;
14      2 4 10 11 13 ;
15      6 7 9 10 11 ;
16      3 4 5 6 11 ;
> A, AV, AE := AutomorphismGroup(G);
> A;
Permutation group aut acting on a set of cardinality 16
Order = 1920 = 2^7 * 3 * 5
    (2, 15)(5, 11)(7, 14)(10, 12)
    (3, 11)(8, 10)(9, 14)(13, 15)
    (2, 11)(5, 15)(6, 8)(9, 16)
    (2, 7)(4, 6)(9, 13)(14, 15)
    (1, 2, 13, 15)(3, 11, 4, 5)(7, 10, 12, 14)(8, 9)
> CompositionFactors(A);
    G
    |  Cyclic(2)
    *
    |  Alternating(5)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    1
> IsPrimitive(A);                                                    
true

> F := FittingSubgroup(A);
> F;
Permutation group F acting on a set of cardinality 16
Order = 16 = 2^4
    (1, 13)(2, 11)(3, 4)(5, 15)(6, 8)(7, 10)(9, 16)(12, 14)
    (1, 10)(2, 9)(3, 12)(4, 14)(5, 8)(6, 15)(7, 13)(11, 16)
    (1, 11)(2, 13)(3, 5)(4, 15)(6, 14)(7, 9)(8, 12)(10, 16)
    (1, 12)(2, 6)(3, 10)(4, 7)(5, 16)(8, 11)(9, 15)(13, 14)

> EARNS(A) eq F;
true

> S1 := Stabilizer(A, AV, V!1);
> #S1;
120
> IsTransitive(S1);
false
> O := Orbits(S1);
> O;
[
    GSet{ 1 },
    GSet{ 2, 3, 5, 7, 9, 11, 13, 14, 15, 16 },
    GSet{ 4, 6, 8, 10, 12 }
]
> IsSymmetric(ActionImage(S1, O[3]));
true