Namespaces
Variants
Actions

Graph automorphism

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

An isomorphic mapping of a graph onto itself (cf. Graph isomorphism). The set of all automorphisms of a given graph forms a group with respect to the operation of composition of automorphisms. The automorphisms of a graph $G$ generate a group $\Gamma(G)$ of permutations of vertices, which is called the group (or vertex group) of $G$, and a group of edge permutations $\Gamma_1(G)$, called the edge group of $G$. The edge group and vertex group of a graph $G$ without loops and multiple edges are isomorphic if and only if $G$ contains not more than one isolated vertex and if none of its connected components is an isolated edge. For each finite group $F$ there exists a graph whose automorphism group is isomorphic to $F$. There also exist permutation groups on a set of $n$ elements which are not the vertex group of any graph with $n$ vertices. Various types and measures of symmetry of a graph can be related to its automorphisms. A graph with no automorphisms other than the identical one is said to be asymmetric. If $n\to\infty$, almost all graphs with $n$ vertices are asymmetric.

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9


Comments

The fact that for a finite group $F$ there is a graph with automorphism group $F$ is due to R. Frucht [a3]. A good reference for this and other algebraic aspects of graph theory is [a1]. A related reference is [a2].

References

[a1] N. Biggs, "Algebraic graph theory" , Cambridge Univ. Press (1974)
[a2] N. Biggs, "Finite groups of automorphisms" , Cambridge Univ. Press (1971)
[a3] R. Frucht, "Herstellung von Graphen mit vorgegebener abstrakter Gruppe" Compos. Math. , 6 (1938) pp. 239–250
How to Cite This Entry:
Graph automorphism. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_automorphism&oldid=52590
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article