GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/AutomorphismGroup

GraphTheory

 AutomorphismGroup
 compute the automorphism group

 Calling Sequence AutomorphismGroup( G, opts )

Parameters

 G - a graph opts - (optional) zero or more options as specified below

Options

 • storage=rectangular, sparse, or auto
 This option controls whether the dense or sparse algorithm from the Nauty library is used. The values rectangular and sparse correspond to the dense and sparse algorithms, respectively, while the value auto automatically chooses which algorithm to employ based on a heuristic depending on the number of vertices and edges in G. The default is auto.

Definition of Automorphism Group

 • Let G be a graph with vertex set V.
 • An automorphism $\mathrm{\sigma }$ of a graph G is a permutation of V such that for any pair of vertices u and v in V, there is a (directed) edge from u to v in G if and only if there is a (directed) edge from $\mathrm{\sigma }\left(u\right)$ to $\mathrm{\sigma }\left(v\right)$.
 • The set of automorphisms of G form a group. The group identity is the automorphism that is the identity mapping on V, and the group operation is function composition.
 • No general polynomial-time algorithm for computing graph automorphisms is presently known.

Details

 • This command makes use of the Nauty library for computing automorphism groups and canonical labelings.

Description

 • The AutomorphismGroup( G ) command computes the group of automorphisms of a given graph G.
 • The automorphism group is represented as a permutation group.
 • The graph G may be directed or undirected, but must be unweighted.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$$\mathrm{with}\left(\mathrm{GroupTheory}\right):$

Compute the automorphism group of the cycle graph on 5 vertices and verify it is isomorphic to the dihedral group D5.

 > $\mathrm{C5}≔\mathrm{CycleGraph}\left(5\right)$
 ${\mathrm{C5}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $G≔\mathrm{AutomorphismGroup}\left(\mathrm{C5}\right)$
 ${G}{≔}⟨\left({1}{,}{2}\right)\left({3}{,}{5}\right){,}\left({2}{,}{5}\right)\left({3}{,}{4}\right)⟩$ (2)
 > $\mathrm{AreIsomorphic}\left(G,\mathrm{DihedralGroup}\left(5\right)\right)$
 ${\mathrm{true}}$ (3)

Compute the automorphism group of the complete graph on 4 vertices and verify it is isomorphic to the symmetric group S4.

 > $\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$
 ${\mathrm{K4}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (4)
 > $G≔\mathrm{AutomorphismGroup}\left(\mathrm{K4}\right)$
 ${G}{≔}⟨\left({1}{,}{2}\right){,}\left({2}{,}{3}\right){,}\left({3}{,}{4}\right)⟩$ (5)
 > $\mathrm{AreIsomorphic}\left(G,\mathrm{SymmetricGroup}\left(4\right)\right)$
 ${\mathrm{true}}$ (6)

Compute the automorphism group of the Petersen graph and display its order.

 > $\mathrm{PG}≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$
 ${\mathrm{PG}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (7)
 > $G≔\mathrm{AutomorphismGroup}\left(\mathrm{PG}\right)$
 ${G}{≔}⟨\left({1}{,}{2}\right)\left({3}{,}{5}\right)\left({6}{,}{9}\right)\left({7}{,}{8}\right){,}\left({2}{,}{5}\right)\left({3}{,}{4}\right)\left({7}{,}{10}\right)\left({8}{,}{9}\right){,}\left({3}{,}{9}\right)\left({4}{,}{8}\right)\left({7}{,}{10}\right){,}\left({4}{,}{7}\right)\left({5}{,}{6}\right)\left({8}{,}{10}\right)⟩$ (8)
 > $\mathrm{GroupOrder}\left(G\right)$
 ${120}$ (9)

Compatibility

 • The GraphTheory[AutomorphismGroup] command was introduced in Maple 2017.