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 is a permutation of the vertex set, such that the pair of vertices form an edge if and only if the pair also form an edge. That is, it is a graph isomorphism from 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]
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
| O((logn)c) | |
| 2 |
c>0
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.[7] 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] [7]
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, BLISS and SAUCY. 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 vertices, the automorphism group can be specified by no more than
n-1
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.
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,[8] or by explicitly identifying symmetries and using them to guide vertex placement in the drawing.[9] 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.
Several families of graphs are defined by having certain types of automorphisms:
Inclusion relationships between these families are indicated by the following table:
| distance-transitive | distance-regular | strongly regular | ||
| symmetric (arc-transitive) | ||||
| (if connected) | ||||
| vertex- and edge-transitive | edge-transitive and regular | edge-transitive | ||
| vertex-transitive | ||||