-
An automorphism is an isomorphism from graph
to itself. The set of automorphisms of forms the Automorphism group . - Clearly, by definition, a group on permutations is a subgroup of the Symmetric Group. Therefore
- For
, the graph obtained by applying is denoted . It is the graph where
- Clearly, by definition, a group on permutations is a subgroup of the Symmetric Group. Therefore
-
(Godsil 1.3.1) If
and , then In other words,
permutes the vertices of equal degree among themselves. Additionally, In a digraph, directions are also preserved.
-
(Godsil 1.3.2) If
and , then In other words Automorphisms preserve distances between vertices.
-
(Godsil 1.3.3)
. (see graph complements). -
Clearly,
. -
. In fact (Godsil e2.2) , -
Proof: This can be shown as follows: Vertex
must map to one of possibilities, say ,. then maps to either or . This can be continued inductively.
-