Automorphism Group of a Graph or Digraph

The automorphism group functionality is an interface to version 2.9.3 of the nauty and Traces packages of B. McKay and A. Piperno. For a paper describing nauty see [McK81]. There also exists a user’s guide [MP] describing the essential features of nauty and Traces. That guide is the Version 2.6 edition, which is the one the page references below point into.

The Automorphism Group Function

AutomorphismGroup(G : parameters): Grph -> GrpPerm, GSet, GSet, PowMap, Map, Grph
Al          : MonStgElt                           Default: "nauty"
Canonical   : BoolElt                             Default: false
Stabilizer  : [ { GrphVert } ]                    Default: 
Invariant   : MonStgElt                           Default: 
Minlevel    : RngIntElt                           Default: 0
Maxlevel    : RngIntElt                           Default: 
Arg         : RngIntElt                           Default: 
TCLevel     : RngIntElt                           Default: 100
Print       : RngIntElt                           Default: 0
Verbosity   : RngIntElt                           Default: 0
IgnoreLabels: BoolElt                             Default: false

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 \(\cal{A}\) of all automorphisms of \(G\), and the transfer map from \(A\) to \(\cal{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 seven principal parameters: Al, Canonical, Stabilizer, Invariant, TCLevel, Print and Verbosity. Some of these parameters have associated parameters.

The parameter Al controls whether the nauty or Traces algorithms are used to compute the automorphism group. Al := "Traces" is rejected when \(G\) is directed, since Traces is not available for digraphs. The parameters Invariant, Minlevel, Maxlevel, Arg and TCLevel are applicable only with the nauty algorithm, and Verbosity only with Traces.

If the parameter Canonical is set to 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. It is important to note that the canonically labelled graph is dependent upon all the parameters used to compute the automorphism group, including the algorithm parameter.

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 is only relevant when the nauty algorithm is used. It causes the algorithm to 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 pages 37–39 of the Version 2.6 nauty and Traces user’s guide [MP].

Invariant has no default of its own, and omitting it is not the same as giving it the value "default". Omitting it inherits the invariant \(G\) is carrying from its last automorphism computation, together with the Minlevel, Maxlevel, Arg and TCLevel that went with it. That is what makes an invariant remembered in the sense of Subsection Graph Colouring and Automorphism Group. On a graph carrying nothing yet, inheriting nothing leaves the default for the kind of graph: no invariant when \(G\) is undirected, and the "adjacencies" invariant when \(G\) is a digraph, which nauty’s own digraph defaults install before any parameter is read.

Invariant := "default" names no invariant of its own and inherits none either, so it is how a remembered invariant is discarded: it returns \(G\) to the default for its kind. On an undirected graph that leaves no invariant in use; on a digraph it leaves "adjacencies", since naming no invariant does not remove the one the digraph defaults supplied. Naming another invariant replaces "adjacencies" rather than removing it, so a digraph always runs with some invariant and no value of Invariant turns the invariant off.

For a more detailed discussion on invariants see Subsection nauty Invariants.

There are three optional associated parameters to Invariant:

Minlevel and Maxlevel bound the levels of the search tree at which the invariant is applied, and Arg is an expression whose meaning depends 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, 999, and 0 respectively. When Invariant is one of “indsets”, “cliques”, “cellcliq”, or “cellind”, the default value for Arg is \(3\). The default for Maxlevel thus depends on the graph and that for Arg on the invariant, and the parameter list above leaves both blank. A call that names an invariant starts from these defaults: unlike a call that leaves Invariant out, it inherits nothing from the last computation on \(G\).

The two levels are not independent. Setting Minlevel and leaving Maxlevel unset does not leave Maxlevel at the default above: Maxlevel is set to the value given for Minlevel, so the invariant is applied at that single level. To apply it over a range of levels, give Maxlevel as well.

Under the nauty algorithm none of these three may be passed on its own: setting Minlevel, Maxlevel or Arg without also setting Invariant to a named invariant is an error, and Invariant := "default" does not count as one. This holds for a digraph as well, even though a digraph applies "adjacencies" by default, so to depart from the digraph defaults above one names that invariant again and writes, for example, Invariant := "adjacencies", Maxlevel := 5. Under Al := "Traces" none of the three is read, so all three are accepted and ignored rather than rejected. Again, see Subsection nauty Invariants for more information.

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 (nauty only).

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

The integer valued parameter Verbosity sets Traces’ own reporting level, the default 0 meaning no output. It is ignored when the nauty algorithm is used.

The integer valued parameter TCLevel is independent of Invariant, and may be set on its own. It is the deepest level of the search tree at which nauty applies its more expensive rule for choosing a target cell; deeper than that the cheap rule is used. The default is 100. This parameter is only relevant when the nauty algorithm is used, and it has no effect when \(G\) is a digraph, for which nauty always uses the cheap rule.

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 999 for digraphs). Giving Minlevel without Maxlevel sets Maxlevel to the value given for Minlevel, rather than leaving it at that default, so the invariant is applied at that one level only

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

Under the nauty algorithm these three can only be set alongside an explicit Invariant: passing any of them with no invariant named is an error, and Invariant := "default" does not count as one. This holds for a digraph too, although a digraph applies "adjacencies" by default. The Traces algorithm reads neither Invariant nor any of the three, so under Al := "Traces" all three are accepted and ignored.

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 accepted values of Invariant are listed below. The first of them, "default", names no invariant of its own, which is why it does not count as a named invariant in the paragraph above. On a digraph it does not disable the "adjacencies" invariant that nauty applies there by default.

"default"

:

•

Default — no invariant is named, and none is inherited: this is how an invariant remembered from an earlier computation on \(G\) is discarded, where omitting Invariant would keep it. On an undirected graph that leaves none in use. On a digraph it leaves in place the "adjacencies" invariant that nauty’s digraph defaults supply, so that invariant is still applied. Naming another invariant replaces "adjacencies" rather than removing it, so no value of Invariant runs nauty on a digraph with no invariant at all.

"twopaths"

:

•

Each vertex is classified according to the vertices reachable from along a path of length \(2\). This is a cheap invariant sometimes useful for regular graphs. Arg is not used.

"adjtriang"

:

•

This counts the number of common neighbours between pairs of adjacent (if Arg = \(0\)) or non–adjacent (if Arg = \(1\)) vertices. This is a fairly cheap invariant which can often work for strongly regular graphs.

"triples"

:

•

This considers in detail the neighbourhoods of each triple of vertices. It often works for strongly regular graphs that "adjtriang" fails on, but is more expensive. Arg is not used.

"quadruples"

:

•

Similar to triples but using quadruples of vertices. Much more expensive but can work on graphs with highly regular structure that "triples" fails on. Arg is not used.

"celltrips"

:

•

Like "triples", but only triples inside one cell are used. One to try for the bipartite incidence graphs of structures like block designs (but won’t work for projective planes). Arg is not used.

"cellquads"

:

•

Like "quadruples", but only quadruples inside one cell are used. Originally designed for some exceptional graphs derived from Hadamard matrices (where applying it at level \(2\) is best). Arg is not used.

"cellquins"

:

•

Considers 5-tuples of vertices inside a cell. Very expensive. We don’t know of a good application. Arg is not used.

"cellfano"

:

"cellfano2"

:

•

These are intended for the bipartite graphs of projective planes and similar highly regular structures. "cellfano2" is cheaper, so try it first. Arg is not used. The method is similar to counting Fano subplanes.

"distances"

:

•

This uses the distance matrix of the graph. It is good at partitioning general regular graphs (but not strongly regular graphs). Moderately cheap. Arg is unused.

"indsets"

:

•

This uses the independent sets of size Arg (default \(3\)). Can be successful for strongly regular graphs (for Arg \(\ge 4\)) or regular bipartite graphs.

"cliques"

:

•

This uses the cliques of size Arg (default \(3\)). Can be successful for strongly regular graphs (for Arg \(\ge 4\)).

"cellind"

:

•

This uses the independent sets of size Arg (default \(3\)) that lie entirely within one cell of the partition. Try applying at level \(2\) for difficult vertex-transitive graphs.

"cellcliq"

:

•

This uses the cliques of size Arg (default \(3\)) that lie entirely within one cell of the partition. Try applying at level \(2\) for difficult vertex-transitive graphs.

"adjacencies"

:

•

This is a simple invariant that corrects for a deficiency in the built-in partition refinement procedure for directed graphs. It is the default in Magma for directed graphs, and Invariant := "default" does not remove it. Apply at a few levels, say levels 1–5; Magma, though, leaves Maxlevel at the nauty digraph default of 999, so unless it is narrowed the invariant is applied at every level. Arg is unused.

"refinvar"

:

•

Each vertex of a cell is individualised in turn and the partition is then partially refined; the refinement reached is that vertex’s invariant. The cells considered are the non-singleton ones, taken in increasing order of size, and the process stops at the first cell whose vertices do not all receive the same invariant. Arg bounds the number of refinement rounds, with \(0\) (the default) placing no bound. Expensive, but it can separate vertices that the cheaper invariants leave in one cell.

These invariants are further described on pages 37–39 of the Version 2.6 nauty and Traces user’s guide [MP]. Also, we provide a facility enabling users to test if a specific Invariant achieves a partition refinement for a graph \(G\).

IsPartitionRefined(G: parameters): Grph -> BoolElt
Stabilizer  : [ { GrphVert } ]                    Default: 
Invariant   : MonStgElt                           Default: 
Arg         : RngIntElt                           Default: 
IgnoreLabels: BoolElt                             Default: false

Returns true if and only if the invariant in Invariant could refine the graph \(G\)’s vertex-set partition. Invariant is read as it is by AutomorphismGroup: omitting it inherits the invariant \(G\) is carrying from its last automorphism computation, and Invariant := "default" discards that, so it is Invariant := "default" rather than omission that tests the built-in refinement procedure.

Four parameters can be passed: Stabilizer, Invariant, Arg and IgnoreLabels.

They have the same meaning as for AutomorphismGroup. Note that Minlevel and Maxlevel are not accepted here.

Graph Colouring and Automorphism Group

For any calls to nauty or Traces 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 or Traces 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

Diameter, DiameterPath, IsDistanceRegular, GirthCycle, Girth

2

IsDistanceTransitive, IsTransitive, IsPrimitive, IsSymmetric, IsIsomorphic, IsEdgeTransitive, EdgeGroup, OrbitsPartition, CanonicalGraph, CanonicalGraphMap

The functions in Group \(1\) make use of the automorphism group of the graph only as a means to improve efficiency. If some group has already been computed for the graph under consideration then this group will be used. Otherwise the graph’s default group is computed.

The functions in Group \(2\) all use the graph’s default group. If a group \(A\) of the graph \(G\) has already been computed but is not \(G\)’s default group (for example if a stabilizer of \(G\) was given when computing \(A\)) then the graph’s default group will be computed. Consequently, as an example, if \(G\) is coloured, IsTransitive(G) will (always) return false.

For all these functions it is possible to drive the group computation by setting an appropriate Invariant parameter. This is particularly useful when it is known that some invariant will speed up the group computation. This is achieved by first computing the group using AutomorphismGroup while setting Invariant. This parameter is then remembered, along with Minlevel, Maxlevel, Arg and TCLevel, for any further (re)computation of the default automorphism group: a later call that names no Invariant inherits it rather than starting from the default for the kind of graph. A later call that names a different invariant replaces it, and Invariant := "default" discards it. For convenience, the function IsIsomorphic accepts a parameter suite very similar to that of the AutomorphismGroup function: It is particularly useful when stabilizers need to be set.

Variants of Automorphism Group

CanonicalGraph(G): Grph -> Grph, GrphVertSet, GrphEdgeSet

Given a graph \(G\), return the canonically labelled graph isomorphic to \(G\), together with its vertex-set and its edge-set. To see which automorphism group is computed see Subsection Graph Colouring and Automorphism Group. Users should be aware that the canonical graph is dependent upon the invariant used when computing the automorphism group. Thus, the computation of the automorphism group of \(G\) using different invariants will produce different canonical labellings.

CanonicalGraphMap(G): Grph -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum

As CanonicalGraph, return the canonically labelled graph isomorphic to \(G\) with its vertex-set and its edge-set, and in addition the labelling that produced it. That fourth return value is a sequence \(m\) of vertices of \(G\), where \(m[i]\) is the vertex of \(G\) that becomes vertex \(i\) of the canonical graph. To see which automorphism group is computed see Subsection Graph Colouring and Automorphism Group. Since the canonical graph depends upon the parameters used to compute the automorphism group, so does \(m\).

EdgeGroup(G): 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\). To see which automorphism group is computed see Subsection Graph Colouring and Automorphism Group.

IsIsomorphic(G, H : parameters): GrphDir, GrphDir -> BoolElt, Map
Al          : MonStgElt                           Default: "nauty"
Stabilizer  : [ { GrphVert } ]                    Default: 
Stabilizer2 : [ { GrphVert } ]                    Default: 
Invariant   : MonStgElt                           Default: 
Minlevel    : RngIntElt                           Default: 0
Maxlevel    : RngIntElt                           Default: 
Arg         : RngIntElt                           Default: 
TCLevel     : RngIntElt                           Default: 100
IgnoreLabels: BoolElt                             Default: false
IsIsomorphic(G, H : parameters): GrphUnd, GrphUnd -> BoolElt, Map
Al          : MonStgElt                           Default: "nauty"
Stabilizer  : [ { GrphVert } ]                    Default: 
Stabilizer2 : [ { GrphVert } ]                    Default: 
Invariant   : MonStgElt                           Default: 
Minlevel    : RngIntElt                           Default: 0
Maxlevel    : RngIntElt                           Default: 
Arg         : RngIntElt                           Default: 
TCLevel     : RngIntElt                           Default: 100
IgnoreLabels: BoolElt                             Default: false

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. Canonical, Print and Verbosity are not accepted: the canonical graph is always computed here, and IsIsomorphic offers no informative printing. Of the rest, Stabilizer and IgnoreLabels differ in meaning, in that each applies to both graphs, and Stabilizer2 has no counterpart in AutomorphismGroup:

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

Stabilizer2, which sets the stabilizer set for the second graph \(H\) only.

IgnoreLabels indicates whether or not to ignore the graph labelling for both graphs \(G\) and \(H\).

The remaining parameters Al, Invariant, Minlevel, Maxlevel, Arg and TCLevel have the same meaning as for AutomorphismGroup, and all but Al are relevant only under the nauty algorithm. Note that Al := "Traces" is rejected when \(G\) and \(H\) are directed, since Traces is not available for digraphs, and that TCLevel has no effect for digraphs.

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.

In general, to see which and how the graphs’ automorphism groups are computed see Subsection Graph Colouring and Automorphism Group.

Example: Automorphism Group and Canonical Graph (ex-bda3f8)

Run in calculator (opens in a new tab)

We provide a very simple example of the use of AutomorphismGroup which shows how the automorphism group and the corresponding canonical graph differ depending on the labelling of the graph and of the stabilizer given, if any.

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

We now check that the graph returned by CanonicalGraph is identical to \(C_1\):

> C4 := CanonicalGraph(G);
> C4 eq C1;
true

Run in calculator (opens in a new tab)

Example: Isomorphism of Coloured Graphs (ex-4bd4fd)

Run in calculator (opens in a new tab)

These two examples should help clarify how IsIsomorphic behaves for graphs for which a colouring is defined. The first example shows that two graphs cannot be isomorphic if one is coloured while the other is not. This example also demonstrates the use of stabilizers.

> 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

The second example shows that two graphs are isomorphic if and only if colours map to the same colours.

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

Run in calculator (opens in a new tab)

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 an 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, GSet, 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 \rightarrow L\), where the permutation group \(L\) gives the action of \(A\) on the set \(Y\). The function returns:

(a)

The natural homomorphism \(\phi: A \rightarrow L\);

(b)

The induced group \(L\);

(c)

The kernel of the action (a subgroup of \(A\)).

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

Given a subgroup \(A\) 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: Automorphisms of the Clebsch Graph (ex-ec7c11)

Run in calculator (opens in a new tab)

We construct the Clebsch graph (a strongly regular graph) and investigate the action of its automorphism group.

> 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

From the composition factors we guess that the group is \(Sym(5)\) extended by the elementary abelian group of order \(16\). Let us verify this and relate it to the graph. We begin by trying to get at the group of order \(16\). We ask for the Fitting subgroup.

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

Since \(A\) is primitive, this looks as if it is an elementary abelian regular normal subgroup:

> EARNS(A) eq F;
true

Thus, \(A\) has a regular normal subgroup \(N\) of order \(16\) which acts transitively on the vertices. Therefore, the stabilizer of any point is a complement of \(N\).

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

So the stabilizer of the vertex \(1\) is \({\Sym}(5)\), acting faithfully on the \(5\) neighbours of vertex \(1\).

Run in calculator (opens in a new tab)