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 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  |
A simple graph whose automorphism group is a cyclic group may be termed a cyclic group graph. The smallest nontrivial cyclic group graphs have nine nodes.
