## Automorphism

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.

## Vertex-transitive Graphs

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.

## Edge-transitive Graphs

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.

## Arc-transtive graphs

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.

## t-arc-transitive graphs

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.*

## Distance-transitive graphs

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.*