Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

Formally, an automorphism of a graph $G = (V, E)$ is a permutation $σ$ of the vertex set $V$ , such that the pair of vertices $(u, v)$ form an edge if and only if the pair $(σ (u), σ (v))$ also form an edge. That is, it is a graph isomorphism from $G$ to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph.^[1]^[2]

Computational complexity

Constructing the automorphism group of a graph, in the form of a list of generators, is polynomial-time equivalent to the graph isomorphism problem, and therefore solvable in quasi-polynomial time, that is with running time $2^{O((\log n)^{c})}$ for some fixed $c>0$ .^[3]^[4] Consequently, like the graph isomorphism problem, the problem of finding a graph's automorphism group is known to belong to the complexity class NP, but not known to be in P nor to be NP-complete, and therefore may be NP-intermediate.

The easier problem of testing whether a graph has any symmetries (nontrivial automorphisms), known as the graph automorphism problem, also has no known polynomial time solution.^[5] There is a polynomial time algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant.^[6] The graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown.^[3]^[7]^[8] By contrast, hardness is known when the automorphisms are constrained in a certain fashion; for instance, determining the existence of a fixed-point-free automorphism (an automorphism that fixes no vertex) is NP-complete, and the problem of counting such automorphisms is ♯P-complete.^[5]^[8]

Algorithms, software and applications

While no worst-case polynomial-time algorithms are known for the general Graph Automorphism problem, finding the automorphism group (and printing out an irredundant set of generators) for many large graphs arising in applications is rather easy. Several open-source software tools are available for this task, including NAUTY,^[9] BLISS^[10] and SAUCY.^[11]^[12] SAUCY and BLISS are particularly efficient for sparse graphs, e.g., SAUCY processes some graphs with millions of vertices in mere seconds. However, BLISS and NAUTY can also produce Canonical Labeling, whereas SAUCY is currently optimized for solving Graph Automorphism. An important observation is that for a graph on $n$ vertices, the automorphism group can be specified by no more than $n-1$ generators, and the above software packages are guaranteed to satisfy this bound as a side-effect of their algorithms (minimal sets of generators are harder to find and are not particularly useful in practice). It also appears that the total support (i.e., the number of vertices moved) of all generators is limited by a linear function of $n$ , which is important in runtime analysis of these algorithms. However, this has not been established for a fact, as of March 2012.

Practical applications of Graph Automorphism include graph drawing and other visualization tasks, solving structured instances of Boolean Satisfiability arising in the context of Formal verification and Logistics. Molecular symmetry can predict or explain chemical properties.

Symmetry display

Several graph drawing researchers have investigated algorithms for drawing graphs in such a way that the automorphisms of the graph become visible as symmetries of the drawing. This may be done either by using a method that is not designed around symmetries, but that automatically generates symmetric drawings when possible,^[13] or by explicitly identifying symmetries and using them to guide vertex placement in the drawing.^[14] It is not always possible to display all symmetries of the graph simultaneously, so it may be necessary to choose which symmetries to display and which to leave unvisualized.

Graph families defined by their automorphisms

Several families of graphs are defined by having certain types of automorphisms:

An asymmetric graph is an undirected graph with only the trivial automorphism.
A vertex-transitive graph is an undirected graph in which every vertex may be mapped by an automorphism into any other vertex.
An edge-transitive graph is an undirected graph in which every edge may be mapped by an automorphism into any other edge.
A symmetric graph is a graph such that every pair of adjacent vertices may be mapped by an automorphism into any other pair of adjacent vertices.
A distance-transitive graph is a graph such that every pair of vertices may be mapped by an automorphism into any other pair of vertices that are the same distance apart.
A semi-symmetric graph is a graph that is edge-transitive but not vertex-transitive.
A half-transitive graph is a graph that is vertex-transitive and edge-transitive but not symmetric.
A skew-symmetric graph is a directed graph together with a permutation σ on the vertices that maps edges to edges but reverses the direction of each edge. Additionally, σ is required to be an involution.

Inclusion relationships between these families are indicated by the following table:

Skeleton of the dodecahedron	Shrikhande graph	Paley graph
distance-transitive	distance-regular	strongly regular

F26A graph	Nauru graph
symmetric (arc-transitive)	t-transitive, t ≥ 2
(if connected)
Holt graph	Folkman graph	Complete bipartite graph K3,5
vertex- and edge-transitive	edge-transitive and regular	edge-transitive

Skeleton of the truncated tetrahedron	Frucht graph
vertex-transitive	regular

Skeleton of the triangular prism
Cayley graph

References

^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
^ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987, S2CID 124723321.
^ ^a ^b Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8 (3): 131–132. doi:10.1016/0020-0190(79)90004-8.
^ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "Graph isomorphisms in quasi-polynomial time". arXiv:1710.04574 [math.GR].
^ ^a ^b Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.
^ Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5.
^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287
^ ^a ^b Torán, Jacobo (2004). "On the hardness of graph isomorphism" (PDF). SIAM Journal on Computing. 33 (5): 1093–1108. doi:10.1137/S009753970241096X. Archived from the original (PDF) on 2008-11-20. Retrieved 2010-03-10.
^ McKay, Brendan (1981), "Practical Graph Isomorphism" (PDF), Congressus Numerantium, 30: 45–87, retrieved 14 April 2011.
^ Junttila, Tommi; Kaski, Petteri (2007), "Engineering an efficient canonical labeling tool for large and sparse graphs" (PDF), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX07).
^ Darga, Paul; Sakallah, Karem; Markov, Igor L. (June 2008), "Faster symmetry discovery using sparsity of symmetries", Proceedings of the 45th annual Design Automation Conference (PDF), pp. 149–154, doi:10.1145/1391469.1391509, ISBN 978-1-60558-115-6, S2CID 15629172, archived from the original (PDF) on 2021-01-26, retrieved 2011-04-14.
^ Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (July 2010), "Symmetry and Satisfiability: An Update" (PDF), Proc. Satisfiability Symposium (SAT).
^ Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry, 7 (1): 381–401, doi:10.1007/BF02187850; Eades, Peter; Lin, Xuemin (2000), "Spring algorithms and symmetry", Theoretical Computer Science, 240 (2): 379–405, doi:10.1016/S0304-3975(99)00239-X.
^ Hong, Seok-Hee (2002), "Drawing graphs symmetrically in three dimensions", Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 106–108, doi:10.1007/3-540-45848-4_16, ISBN 978-3-540-43309-5.

External links

Weisstein, Eric W. "Graph automorphism". MathWorld.

[1] Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.

[2] Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987, S2CID 124723321.

[mathon-3] Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8 (3): 131–132. doi:10.1016/0020-0190(79)90004-8.

[4] Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (October 12, 2017). "Graph isomorphisms in quasi-polynomial time". arXiv:1710.04574 [math.GR].

[lubiw81-5] Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.

[luks82-6] Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5.

[7] Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287

[t04-8] Torán, Jacobo (2004). "On the hardness of graph isomorphism" (PDF). SIAM Journal on Computing. 33 (5): 1093–1108. doi:10.1137/S009753970241096X. Archived from the original (PDF) on 2008-11-20. Retrieved 2010-03-10.

[9] McKay, Brendan (1981), "Practical Graph Isomorphism" (PDF), Congressus Numerantium, 30: 45–87, retrieved 14 April 2011.

[10] Junttila, Tommi; Kaski, Petteri (2007), "Engineering an efficient canonical labeling tool for large and sparse graphs" (PDF), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX07).

[11] Darga, Paul; Sakallah, Karem; Markov, Igor L. (June 2008), "Faster symmetry discovery using sparsity of symmetries", Proceedings of the 45th annual Design Automation Conference (PDF), pp. 149–154, doi:10.1145/1391469.1391509, ISBN 978-1-60558-115-6, S2CID 15629172, archived from the original (PDF) on 2021-01-26, retrieved 2011-04-14.

[12] Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (July 2010), "Symmetry and Satisfiability: An Update" (PDF), Proc. Satisfiability Symposium (SAT).

[13] Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry, 7 (1): 381–401, doi:10.1007/BF02187850; Eades, Peter; Lin, Xuemin (2000), "Spring algorithms and symmetry", Theoretical Computer Science, 240 (2): 379–405, doi:10.1016/S0304-3975(99)00239-X.

[14] Hong, Seok-Hee (2002), "Drawing graphs symmetrically in three dimensions", Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 106–108, doi:10.1007/3-540-45848-4_16, ISBN 978-3-540-43309-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]