- Graph automorphism
In graph-theoretical mathematics, 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 for any edge "e" = ("u","v"), σ("e") = (σ("u"),σ("v")) is also an edge. That is, it is agraph isomorphism from "G" to itself. Automorphisms may be defined in this way both fordirected graph s and forundirected graph s. Theidentity mapping of a graph onto itself is called thetrivial automorphism of the graph.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.Computational complexity
Constructing the automorphism group is at least as difficult (in terms of its
computational complexity ) as solving thegraph isomorphism problem , determining whether two given graphs correspond vertex-for-vertex and edge-for-edge. For, "G" and "H" are isomorphic if and only if the disconnected graph formed by thedisjoint union of graphs "G" and "H" has an automorphism that swaps the two components. [citation|last=Luks|first=Eugene M.|title=Isomorphism of graphs of bounded valence can be tested in polynomial time|journal=Journal of Computer and System Sciences|volume=25|year=1982|pages=42–65|issue=1|doi=10.1016/0022-0000(82)90009-5.]The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism. It belongs to the
class NP of computational complexity. Similar to the graph isomorphism problem, it is unknown whether it has apolynomial time algorithm or it isNP-complete . [A. Lubiw, "Some NP-complete problems similar to Graph Isomorphism",SIAM Journal on Computing , 1O:ll-21, 1981.]ymmetry 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, [citation|first1=Giuseppe|last1=Di Battista|first2=Roberto|last2=Tamassia|first3=Ioannis G.|last3=Tollis|title=Area requirement and symmetry display of planar upward drawings|journal=Discrete and Computational Geometry|volume=7|issue=1|year=1992|pages=381–401|doi=10.1007/BF02187850; citation|first1=Peter|last1=Eades|first2=Xuemin|last2=Lin|title=Spring algorithms and symmetry|journal=Theoretical Computer Science|volume=240|issue=2|year=2000|pages=379–405|doi=10.1016/S0304-3975(99)00239-X.] or by explicitly identifying symmetries and using them to guide vertex placement in the drawing. [citation|first=Seok-Hee|last=Hong|contribution=Drawing graphs symmetrically in three dimensions|title=Proc. 9th Int. Symp. Graph Drawing (GD 2001)|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|year=2002|volume=2265|doi=10.1007/3-540-45848-4_16|pages=106–108.] 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.
*Avertex-transitive graph is an undirected graph in which, for every pair of vertices "u" and "v", there is an automorphism mapping "u" to "v".
*Anedge-transitive graph is an undirected graph in which, for every pair of edges "e" and "f", there is an automorphism mapping "e" to "f".
*Asymmetric graph is a graph that is both vertex-transitive and edge-transitive.
*Anarc-transitive graph is an undirected graph, in which any pair of a vertex "u" and an edge "(u,v)" may be mapped by an automorphism to any other such pair.
*Adistance-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.
*Asemi-symmetric graph is a graph that is edge-transitive but not vertex-transitive.
*Askew-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 aninvolution .References
Wikimedia Foundation. 2010.