Namespaces
Variants
Actions

Difference between revisions of "Graph automorphism"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
(Category:Combinatorics)
Line 1: Line 1:
 
{{TEX|done}}
 
{{TEX|done}}
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 $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.
+
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====
 
====References====
Line 12: Line 12:
 
====References====
 
====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>
 
<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>
 +
 +
[[Category:Combinatorics]]

Revision as of 14:36, 18 October 2014

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=33230
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article