In the mathematical field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an automorphism of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is a form of symmetry in which the graph is mapped onto itself while preserving the edge–

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

connectivity. Formally, an automorphism of a graph is a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

of the vertex set , such that the pair of vertices form an edge

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bi ...

the pair also form an edge. That is, it is a

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) ...

from to itself. Automorphisms may be defined in this way both for

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

s 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 In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

Computational complexity

Constructing the automorphism group is at least as difficult (in terms of its

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

) as solving the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational comp ...

, determining whether two given graphs correspond vertex-for-vertex and edge-for-edge. For, and are isomorphic if and only if the disconnected graph formed by the disjoint union of graphs and has an automorphism that swaps the two components.. In fact, just counting the automorphisms is polynomial-time equivalent to graph isomorphism. Petersen1 tiny

The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism. It belongs to the

class NP In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proof ...

of computational complexity. Similar to the graph isomorphism problem, it is unknown whether it has a

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm or it is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

.. There is a

algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant. The graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown. 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 The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: *The problem i ...

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
NAUTYBLISS
an
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

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 , 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 In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfi ...

arising in the context of

Formal verification In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal met ...

and

Logistics Logistics is generally the detailed organization and implementation of a complex operation. In a general business sense, logistics manages the flow of goods between the point of origin and the point of consumption to meet the requirements of ...

Molecular symmetry Molecular symmetry in chemistry describes the symmetry present in molecules and the classification of these molecules according to their symmetry. Molecular symmetry is a fundamental concept in chemistry, as it can be used to predict or explain ...

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, or by explicitly identifying symmetries and using them to guide vertex placement in the drawing.. 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 In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

is an undirected graph in which every vertex may be mapped by an automorphism into any other vertex. *An

edge-transitive graph In the mathematical field of graph theory, an edge-transitive graph is a graph such that, given any two edges and of , there is an automorphism of that maps to . In other words, a graph is edge-transitive if its automorphism group acts ...

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 In the mathematical field of graph theory, a half-transitive graph is a graph that is both vertex-transitive and edge-transitive, but not symmetric. In other words, a graph is half-transitive if its automorphism group acts transitively upon both ...

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:

References

External links