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 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 (conversely, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph[1]).
Contents |
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 smallest asymmetric cubic graph is the Frucht graph discovered in 1939.[2][3]
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".[4] In contrast, again informally, "almost all infinite graphs are symmetric".[5] More specifically, countable infinite random graphs in the Erdős–Rényi model are, with probability 1, isomorphic to the highly symmetric Rado graph.
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.[6]
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.[7] 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.[8][9] For a reduction in the other direction see lecture by V. Arvind.[10]
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,[11] or by explicitly identifying symmetries and using them to guide vertex placement in the drawing.[12] 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:
- 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:
See also
References
- ^ R.Frucht. Graphs of Degree 3 with given abstract group, Canad. J. Math. 3 1949.
- ^ Frucht, R. "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compos. Math. 6, 239-250, 1939
- ^ Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
- ^ "Algebraic Graph Theory", by Christopher David Godsil, Gordon Royle (2001) ISBN 0387952209
- ^ Erdős, P.; Rényi, A. (1963), "Asymmetric graphs", Acta Mathematica Hungarica 14 (3): 295–315, doi:, http://www.math-inst.hu/~p_erdos/1963-04.pdf
- ^ 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.
- ^ www.cmi.ac.in/~ramprasad/lecturenotes/algcomp/lecture2.pdf
- ^ 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:.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
