Subsections

• The Automorphism Group Function
• Variants of Automorphism Group
• Action of Automorphisms

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.

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

Compute the automorphism group of the graph G according to the parameters parameters. There are five principal parameters: Canonical, Stabilizer, Invariant, TCLevel 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: [ { Vert } ]            Default: Null

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. There is one optional associated Boolean parameter (Ordering) with default value true.

    Invariant: MonStgElt                Default: Null

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.

There are three optional associated parameters:

    Minlevel: RngIntElt                 Default: 0

    Maxlevel: RngIntElt                 Default: 0

    Arg: RngIntElt                      Default: 0

An expression, depending upon the type of invariant.

    TCLevel: RngIntElt                  Default: 6

Specify the rule used to select the target cell by using the integer parameter TCLevel (see p6 of the nauty manual).

    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. 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.

Given a graph G, return the canonically labelled graph isomorphic to G. The parameters parameters are identical to those for AutomorphismGroup.

Returns the automorphism group of the graph G in its action on the edges of G, and the G-set of edges of G.

IsIsomorphic(G, H) : 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 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.

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.

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.

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.

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).

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.

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.

> 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