TOPICS
Search

Graph Automorphism


An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph G back to vertices of G such that the resulting graph is isomorphic with G. The set of automorphisms defines a permutation group known as the graph's automorphism group. For every group Gamma, there exists a graph whose automorphism group is isomorphic to Gamma (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 G 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"].

GraphAutomorphismGridGraph

For example, the grid graph G_(2,3) 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,

 |Aut(G_(m,n))|={1   for m=n=1; 2   for m=1 or n=1; 4   for m!=n and m,n>1; 8   for m=n>1.
(1)
GraphAutomorphismStar

Similarly, the star graph S_4 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, |Aut(S_n)|=(n-1)! for n>=3.

The following table summarizes |Aut(G_n)| for various classes of graphs.

graphOEISsequence
antiprism graph, n>=3A12435448, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
complete graph K_nA0000001, 2, 6, 24, 120, 720, ...
cycle graph C_n, n>=3A0000006, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, ...
hypercube graph Q_nA0001652, 8, 48, 384, 3840, 46080, 645120, 10321920, ...
Möbius ladder, n>=3A00000072, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
prism graph, n>=3A12435112, 48, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, ...
wheel graph W_n, n>=4A00000024, 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 n=1, 2, ... nodes is given by

 1
2 2
2 2 6 6
2 2 2 4 4 6 6 8 8 24 24
2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 6 6 8 8 8 8 10......12 12 12 12 12 12 24 24 120 120
(2)

(OEIS A075094).

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

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

|Aut(G)|OEIScounts of graphs with 1, 2, ... nodes
1A0034000, 0, 0, 0, 0, 8, 152, 3696, 135004, ...
2A0750950, 2, 2, 3, 11, 46, 354, 4431, 89004, ...
30, 0, 0, 0, 0, 0, 0, 0, 4, ...
4A0750960, 0, 0, 2, 6, 36, 248, 2264, 31754, ...
6A0750970, 0, 2, 2, 2, 8, 38, 252, 3262, ...
8A0750980, 0, 0, 2, 4, 14, 74, 623, 7003, ...
100, 0, 0, 0, 1, 2, 2, 4, 16, ...
12A0958530, 0, 0, 0, 6, 18, 70, 446, 3924, ...
140, 0, 0, 0, 0, 0, 2, 4, 4, ...
16A0958540, 0, 0, 0, 0, 6, 20, 164, 1280, ...
180, 0, 0, 0, 0, 0, 0, 0, 4, ...
200, 0, 0, 0, 0, 0, 4, 12, 42, ...
24A0958550, 0, 0, 2, 2, 2, 24, 170, 1570, ...
320, 0, 0, 0, 0, 0, 0, 24, 176, ...
36A0958560, 0, 0, 0, 0, 2, 6, 22, 164, ...
48A0958570, 0, 0, 0, 0, 8, 28, 96, 660, ...
72A0958580, 0, 0, 0, 0, 2, 4, 28, 179, ...
1200, 0, 0, 0, 2, 2, 2, 6, 26, ...
1440, 0, 0, 0, 0, 0, 6, 24, 78, ...
2400, 0, 0, 0, 0, 0, 6, 16, 70, ...
7200, 0, 0, 0, 0, 2, 2, 8, 22, ...
GraphAutomorphismCyclicGroups

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 C_3, namely the graph obtained from the (9, 3)-configuration (second top figure). Other graphs whose automorphism groups are isomorphic to the cyclic group C_3 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 n 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 E_n and C_n denote the empty graph and cyclic graph on n nodes, respectively. Let G_1 union G_2 denote graph union, and G^' denote the graph complement of G. In addition, let A_n be the graph with vertices {a_i,b_i,c_i:0<=i<n} and edges {(a_i,a_(i+1)),(a_i,b_i),(a_i,c_i),(b_i,c_i),(c_i,a_(i+1)):0<=i<n}, where all indices are to be read modulo n (i.e., A_n is made up of an n-gon (a_0,...,a_(n-1)) with a rectangle drawn over each side plus one diagonal in each rectangle). Let (A_n)/m be the graph obtained from A_n by identifying b_i with every b_j where i is congruent j modulo (n/m), and likewise for the c_i. Also let B_n be the graph with vertices {a_i,b_i:0<=i<n} and edges {(a_i,a_(i+1)),(a_i,b_(i-1)),(a_i,b_i),(a_i,b_(i+1)),(a_i,b_(i+3)):0<=i<n}, where all indices are taken modulo n (Voss 2003).

|Aut(G)|graph G|G|
1E_00
2E_22
3A_39
4K_2 union E_24
5A_515
6C_33
7B_714
8C_44
9(A_9)/315
10C_55
11B_(11)22
12C_3 union E_25
13B_(13)26
14C_77
15(A_(15))/521
16C_4 union E_26
17B_(17)34
18C_99
19B_(19)38
20C_5 union E_27
21B_7 union A_323
22C_(11)11
23B_(23)46
24E_44
25A_5 union A_5^'30
26C_(13)13
27(A_9)/3 union A_324
28C_7 union E_29
29B_(29)58
30A_3 union C_514
31B_(31)62

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


See also

Automorphism Group, Edge Automorphism, Edge Automorphism Group, Edge-Transitive Graph, Frucht Graph, Graph Isomorphism, Isomorphic Graphs, Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

Darga, P. T.; Sakallah, K. A.; and Markov, I. L. "Faster Symmetry Discovery using Sparsity of Symmetries." Proceedings of the 45th Design Automation Conference, Anaheim, California, June 2008. 2008. http://vlsicad.eecs.umich.edu/BK/SAUCY/saucy-dac08.pdf.Douglas, B. L. and Wang, J. B. "A Classical Approach to the Graph Isomorphism Problem Using Quantum Walks." J. Phys. A: Math. Theor. 41, 075303-1-15, 2008.Duijvestijn, A. J. W. "Algorithmic Calculation of the Order of the Automorphism Group of a Graph." Memorandum No. 221. Enschede, Netherlands: Twente Univ. Technology, 1978.Frucht, R. "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compos. Math. 6, 239-250, 1939.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Lauri, J. and Scapellato, R. Topics in Graph Automorphisms and Reconstruction. Cambridge, England: Cambridge University Press, 2003.Lipton, R. J.; North, S. C.; and Sandberg, J. S. "A Method for Drawing Graphs." In Proc. First Annual Symposium on Computation Geometry (Ed. J. O'Rourke). New York: ACM Press, pp. 153-160, 1985.McKay, B. "The Nauty Page." http://cs.anu.edu.au/~bdm/nauty/.Skiena, S. "Automorphism Groups." §5.2.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 184-187, 1990.Sloane, N. J. A. Sequences A000165/M1878, A003400/M4575, A075095, A075096, A075097, A075098, A080803, A095348, A124351, and A124354 in "The On-Line Encyclopedia of Integer Sequences."University of Michigan Electrical Engineering and Computer Science department. "Saucy: Fast Symmetry Discovery." http://vlsicad.eecs.umich.edu/BK/SAUCY/.Voss, J. "Re: RE: Graphs with automorphism groups of given order." seqfan@ext.jussieu.fr mailing list. March 27, 2003.

Referenced on Wolfram|Alpha

Graph Automorphism

Cite this as:

Weisstein, Eric W. "Graph Automorphism." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphAutomorphism.html

Subject classifications