Graph Automorphism

An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph back to vertices of such that the resulting graph is isomorphic with . The set of automorphisms defines a permutation group known as the graph's automorphism group. For every group , there exists a graph whose automorphism group is isomorphic to (Frucht 1939; Skiena 1990, p. 185). The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties.

The group of graph automorphisms of a graph may be computed in the Wolfram Language using GraphAutomorphismGroup[g], the elements of which may then be extracted using GroupElements. A number of software implementations exist for computing graph automorphisms, including nauty by Brendan McKay and SAUCY2, the latter of which performs several orders of magnitude faster than other implementations based on empirical tests (Darga et al. 2008).

Precomputed automorphisms for many named graphs can be obtained using GraphData[graph, "Automorphisms"], and the number of automorphisms using GraphData[graph, "AutomorphismCount"].

For example, the grid graph has four automorphisms: (1, 2, 3, 4, 5, 6), (2, 1, 4, 3, 6, 5), (5, 6, 3, 4, 1, 2), and (6, 5, 4, 3, 2, 1). These correspond to the graph itself, the graph flipped left-to-right, the graph flipped up-down, and the graph flipped left-to-right and up-down, respectively, illustrated above. More generally, as is clear from its symmetry,

(1)

Similarly, the star graph has six automorphisms: (1, 2, 3, 4), (1, 3, 2, 4), (2, 1, 3, 4), (2, 3, 1, 4), (3, 1, 2, 4), (3, 2, 1, 4), illustrated above. More generally, as is clear from its symmetry, for .

The following table summarizes for various classes of graphs.

graph	OEIS	sequence
antiprism graph,	A124354	48, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
complete graph	A000000	1, 2, 6, 24, 120, 720, ...
cycle graph ,	A000000	6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, ...
hypercube graph	A000165	2, 8, 48, 384, 3840, 46080, 645120, 10321920, ...
Möbius ladder,	A000000	72, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
prism graph,	A124351	12, 48, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
wheel graph ,	A000000	24, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, ...

The automorphism group of a graph complement is the same as that for the original graph. A graph possessing only a single automorphism is called an identity graph (Holton and Sheehan 1993, p. 24), or sometimes an asymmetric graph. The triangle of sorted lengths of the automorphism graphs on , 2, ... nodes is given by

(2)

(OEIS A075094).

The number of distinct orders for the automorphisms groups of simple graphs on , 2, ... are 1, 1, 2, 5, 8, 14, 19, 30, 45, ... (OEIS A095348).

The following table gives counts of the numbers of -node simple graphs having given automorphism group orders.

	OEIS	counts of graphs with 1, 2, ... nodes
1	A003400	0, 0, 0, 0, 0, 8, 152, 3696, 135004, ...
2	A075095	0, 2, 2, 3, 11, 46, 354, 4431, 89004, ...
3		0, 0, 0, 0, 0, 0, 0, 0, 4, ...
4	A075096	0, 0, 0, 2, 6, 36, 248, 2264, 31754, ...
6	A075097	0, 0, 2, 2, 2, 8, 38, 252, 3262, ...
8	A075098	0, 0, 0, 2, 4, 14, 74, 623, 7003, ...
10		0, 0, 0, 0, 1, 2, 2, 4, 16, ...
12	A095853	0, 0, 0, 0, 6, 18, 70, 446, 3924, ...
14		0, 0, 0, 0, 0, 0, 2, 4, 4, ...
16	A095854	0, 0, 0, 0, 0, 6, 20, 164, 1280, ...
18		0, 0, 0, 0, 0, 0, 0, 0, 4, ...
20		0, 0, 0, 0, 0, 0, 4, 12, 42, ...
24	A095855	0, 0, 0, 2, 2, 2, 24, 170, 1570, ...
32		0, 0, 0, 0, 0, 0, 0, 24, 176, ...
36	A095856	0, 0, 0, 0, 0, 2, 6, 22, 164, ...
48	A095857	0, 0, 0, 0, 0, 8, 28, 96, 660, ...
72	A095858	0, 0, 0, 0, 0, 2, 4, 28, 179, ...
120		0, 0, 0, 0, 2, 2, 2, 6, 26, ...
144		0, 0, 0, 0, 0, 0, 6, 24, 78, ...
240		0, 0, 0, 0, 0, 0, 6, 16, 70, ...
720		0, 0, 0, 0, 0, 2, 2, 8, 22, ...

The smallest nontrivial graph whose automorphism group is cyclic has nine nodes. The one illustrated by Harary (1994, p. 170; left top figure above) is implemented as GraphData["SmallestCyclicGroupGraph"]. However, there is at least one other graph on nine nodes whose automorphism group is isomorphic to the cyclic group , namely the graph obtained from the (9, 3)-configuration (second top figure). Other graphs whose automorphism groups are isomorphic to the cyclic group include three of the Paulus graphs (each on 26 vertices), the 12th fullerene graph on 40 vertices, and Tutte's graph (on 46 vertices). These and other graphs whose automorphism groups are isomorphic to cyclic groups are illustrated in the remaining figures above.

The numbers of vertices of the minimal graph having an automorphism group of order are 0, 2, 9, 4, 15, 3, 14, 4, 15, 5, ... (OEIS A080803). The graphs achieving these bounds are summarized in the following table, where and denote the empty graph and cyclic graph on nodes, respectively. Let denote graph union, and denote the graph complement of . In addition, let be the graph with vertices and edges , where all indices are to be read modulo (i.e., is made up of an -gon with a rectangle drawn over each side plus one diagonal in each rectangle). Let be the graph obtained from by identifying with every where is congruent modulo , and likewise for the . Also let be the graph with vertices and edges , where all indices are taken modulo (Voss 2003).

	graph
1		0
2		2
3		9
4		4
5		15
6		3
7		14
8		4
9		15
10		5
11		22
12		5
13		26
14		7
15		21
16		6
17		34
18		9
19		38
20		7
21		23
22		11
23		46
24		4
25		30
26		13
27		24
28		9
29		58
30		14
31		62

The following table gives the graph automorphisms groups for a number of common graphs.

complete graph	symmetric group
empty graph	symmetric group
cycle graph ,	dihedral group
	finite group C2×C2
,	finite group
as defined above	cyclic group
as defined above	cyclic group