View source for Graph automorphism

An isomorphic mapping of a graph onto itself (cf. [[Graph isomorphism|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448701.png" /> generate a group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448702.png" /> of permutations of vertices, which is called the group (or vertex group) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448703.png" />, and a group of edge permutations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448704.png" />, called the edge group of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448705.png" />. The edge group and vertex group of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448706.png" /> without loops and multiple edges are isomorphic if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448707.png" /> contains not more than one isolated vertex and if none of its connected components is an isolated edge. For each finite group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448708.png" /> there exists a graph whose automorphism group is isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g0448709.png" />. There also exist permutation groups on a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487010.png" /> elements which are not the vertex group of any graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487011.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487012.png" />, almost all graphs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487013.png" /> vertices are asymmetric.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,   "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR></table>



====Comments====
The fact that for a finite group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487014.png" /> there is a graph with automorphism group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044870/g04487015.png" /> is due to R. Frucht [[#References|[a3]]]. A good reference for this and other algebraic aspects of graph theory is [[#References|[a1]]]. A related reference is [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N. Biggs,   "Algebraic graph theory" , Cambridge Univ. Press  (1974)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  N. Biggs,   "Finite groups of automorphisms" , Cambridge Univ. Press  (1971)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R. Frucht,   "Herstellung von Graphen mit vorgegebener abstrakter Gruppe"  ''Compos. Math.'' , '''6'''  (1938)  pp. 239–250</TD></TR></table>