An automorphism of a graph is a bijective map that preserves adjacency, i.e. if then .
Example 1. An automorphism of the square graph defined by the permutation .
An automorphism of a graph can be seen as a permutation over its set of vertices . The Example 1 shows an automorphism of the square graph, which is denoted by the permuation (in cycle notation). Notice that , and are also automorphisms of the square graph.
Example 2. The automorphisms of the square graph defined by the permutations , and .
Here, we have two interesting questions:
- Do all graphs have any automorphism?
- What is the maximum number of automorphisms that a graph can have?
The answer of the first question is yes, all graphs have at least the
trivial automorphism, denoted by ,
that maps each vertex to itself. As we can see in the Example 2, .
Turning now to the second question, since an automorphism is defined by a permutation over ,
then a graph has at most automorphisms, it is the number of permutations over .
For instance, the set of automorphisms of the square graph is , where and .
In particular, for the complete graph of vertices, i.e. , any permutation over define an automorphism, for instance .
Example 3. The complete graph and where , , , .
Lectors familiarized with algebraic groups can see that has a group structure with respect to the composition of functions, where is the identity element. In fact, is a subgroup of the symmetric group which consists of the set of all permutations of a set.
A graph is vertex-transitive if there is an automorphims between any two of its vertices, i.e. for all , there exists such that . Notice that the graph of Example 1 is vertex-transitive. Now, look at the graph of Example 4, is it vertex-transitive?.
Example 4. The 3-path graph with the automorphism and
Roughly speaking, all vertices in a vertex-transive graph have the same “graph perpective”. In Example 4, vertices and are the end points of the 3-path, then they have the same “graph perpective”. In fact, defines an automorphism between these vertices. By the other hand, the vertex is an internal vertex of the 3-path, then it has a different “graph perpective” and it is not possible define automorphism over the 3-path that maps the vertex to the vertex or . Therefore, the 3-path is not vertex-transitive.
In general, all vertex-transitive graph are regular but not all regular graphs are vertex-transitive.
A graph is edge-transitive if there is an automorphism between any two edges, i.e. for all , there exists such that or .
From Example 4, and , therefore the 3-path graph is edge-transitive. Following a similiar approach it can be showed that the square graph (see Example 1) is also edge-transitive.
Example 5. A graph with the automorphisms , , and for .
Let see if the graph of Example 5 is edge-transitive. Let , and be subsets of , such that where , and . We have that:
- defines an automorphism from edges in to edges in , e.g. and .
- defines an automorphism between edges in and , e.g. and . Similarly, and .
- defines an automorphism between edges in . e.g. , .
Since edges in are part of two cycles of length 4 and edges in are part of two cycles of length 4 and 5, then it is not possible define an automorphism between them. Therefore, the graph of Example 5 is not edge-transitive. Intuitively, it means that edges in sets and have a different “graph perpectives”. In contrast, this graph is vertex-transitive, note that all nodes are part of two cycles of length 4 and 5, then all nodes have the same “graph perpective”.
In contrast with vertex-transitive graphs, edge-transitive graphs are not necessarilly regular. However, if a graph is regular and edge-transitive, then it is also vertex-transitive.
A graph is arc-transitive (also called symmetric or flag-transitive) if there is an automorphism between any two edges, i.e. for all , there exists such that and . Notice that this condition is stronger that the edge-transitive condition.
For instance, in the 3-path graph (see Example 4), edge is maped to vertices in edge through the permutation , it is . However, there is not automorphism such that . Therefore, the 3-path is edge-transitive but not arc-transitive. By the other hand, the square-graph (see Example 1 and 2) and the 3-complete graph (see Example 3) are arc-transitive.
In general, arc-transitive graphs are vertex and edge-transitive, however, there are vertex and edge-transitive graphs with odd degree that are not arc-transitive. These graps are called semi-simetric or half-transitive. The smallest known semi-symmetric graph is the Holt graph discovered by Derek Holt in the seventies.
A graph is t-arc-transitive, also called t-transitive, if there is an automorphism between any t-arcs but not (t+1)-arcs, i.e. for all two t-arcs and , there exists such that for .
Example 6. The Möbius–Kantor graph is 2-arc-transitive.
A graph is distance transitive, if there is an automorphism between any two pair of vertice that are at the same distance, i.e. for all , such that , there exists such that and .
Example 6. The Petersen graph is distance transitive.