Graph automorphism
From Wikipedia, the free encyclopedia
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 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.
Contents |
[edit] Asymmetric graphs
The identity mapping of a graph onto itself is called the trivial automorphism of the graph. An asymmetric graph is a graph which has only the trivial automorphism.
The smallest asymmetric non-trivial graphs have 6 vertices.
The proportion of graphs on n vertices with nontrivial automorphism tends to zero as n grows, which is informally expressed as "almost all graphs are asymmetric".[1]
[edit] Computational complexity
Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph 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 the disjoint union of graphs G and H has an automorphism that swaps the two components.[2]
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 a polynomial time algorithm or it is NP-complete. [3] It is known that the graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown.[4][5]
[edit] 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,[6] or by explicitly identifying symmetries and using them to guide vertex placement in the drawing.[7] 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.
[edit] Graph families defined by their automorphisms
Several families of graphs are defined by having certain types of automorphisms.
- A vertex-transitive graph is an undirected graph in which, for every pair of vertices u and v, there is an automorphism mapping u to v.
- An edge-transitive graph is an undirected graph in which, for every pair of edges e and f, there is an automorphism mapping e to f.
- 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 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.
[edit] References
- ^ "Algebraic Graph Theory", by Christopher David Godsil, Gordon Royle (2001) ISBN 0387952209
- ^ 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:.
- ^ A. Lubiw, "Some NP-complete problems similar to Graph Isomorphism", SIAM Journal on Computing, 1O:ll-21, 1981.
- ^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131-132
- ^ Köbler, Johannes; Uwe Schöning, Jacobo Torán (1993). Graph Isomorphism Problem: The Structural Complexity. Birkhäuser Verlag. ISBN 0817636803. OCLC 246882287.
- ^ 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:; Eades, Peter; Lin, Xuemin (2000), "Spring algorithms and symmetry", Theoretical Computer Science 240 (2): 379–405, doi:.
- ^ Hong, Seok-Hee (2002), "Drawing graphs symmetrically in three dimensions", Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, 2265, Springer-Verlag, pp. 106–108, doi:.
