Skip to main content

Section 12.5 Automorphisms of graphs

This section is intended as optional enrichment material. In the current edition, no exercises are included. The main goal of this section is to make you aware of some interesting results involving automorphisms of graphs, without actually studying them in any detail.

Definition 12.5.1.
An automorphism of a graph \(G=(V,E)\) is an isomorphism from \(G\) to \(G\text{.}\) More precisely, it is a bijection \(\varphi\) from \(V\) to \(V\) such that for any \(v,w \in V\text{,}\) we have
\begin{equation*} \{v,w\} \in E \Leftrightarrow \{\varphi(v),\varphi(w)\} \in E. \end{equation*}

The following graph (\(C_4\)) has \(8\) automorphisms. It can be left alone; rotated by \(90^\circ, 180^\circ,\) or \(270^\circ\) or reflected through the vertical, horizontal, or either diagonal axis.

Observe that leaving a graph alone: that is, mapping every vertex to itself, is always an automorphism of any graph. We call this the trivial automorphism.

There are many interesting problems and results relating to automorphisms of graphs. In this section we have chosen a few topics to focus on from this broad field. The first topic is the distinguishing number of graphs. Although this idea had appeared previously, broad interest in it (and the origin of this terminology) began with a paper by Michael Owen Albertson (1946—2009) and Karen Linda Collins (1959—) from \(1996\text{,}\) in which they provided the basic definitions and some initial results.

Definition 12.5.3.
Suppose that a colour has been assigned to each vertex of a graph \(G\text{.}\) An automorphism \(\varphi\) of \(G\) is said to preserve the colouring if for every \(v \in V(G)\text{,}\) the colour of \(v\) is the same as the colour of \(\varphi(v)\text{.}\)

Only the trivial automorphism, and reflection through the vertical axis, preserve the colouring of \(C_4\) shown below.

Definition 12.5.5.
The distinguishing number of a graph is the smallest number of colours required to colour the vertices of that graph so that the trivial automorphism is the only automorphism that preserves the colouring.

Albertson and Collins posed the problem of finding the distinguishing number of any graph.

One of the very early results in probabilistic graph theory (a technique mentioned in Section 11.5) was a theorem by Pál Erdős (1913—1996) and Alfréd Rényi (1921—1970) that almost every graph has only the trivial automorphism. More precisely, what they showed is that if you choose a finite graph completely at random, then the probability is \(1\) that the graph you chose has no automorphisms other than the trivial automorphism. Erdős and Rényi's result immediately implies that almost every graph has a distinguishing number of \(1\text{:}\) we can colour every vertex black, and still only the trivial automorphism preserves this colouring, since it is the only automorphism of the graph.

Despite the Erdős-Rényi result, there are many interesting families of graphs (such as the cycles \(C_n\)) that have plenty of nontrivial automorphisms. Although (by Erdős and Rényi's result) the number of such graphs is vanishingly small as a proportion of all possible graphs, they nonetheless exist, and finding their distinguishing number is an interesting problem.

For the cycle \(C_n\text{,}\) the problem of finding the distinguishing number is equivalent to asking if you have a set of \(n\) identical keys on a key ring, and you apply coloured covers to some of them, how many colours of covers do you need to ensure that you can tell all of your keys apart from each other? This question has some strong relationships to one of the enumeration questions we considered much earlier in this course: how many beaded necklaces can be made with a collection of coloured beads?

We begin by considering \(C_5\text{.}\)

The cycle \(C_5\) has a distinguishing number of \(3\text{.}\)

To see that two colours are not sufficient, note that if two colours are used then one of the colours must be used on \(1\) or \(2\) of the vertices, while the other colour is used on the remaining \(4\) or \(3\) vertices. In either case, some case-by-case analysis shows that there is a reflection that preserves the colouring.

To see that three colours are sufficient, observe this colouring:

The only nontrivial automorphism that fixes the white vertex is reflection through the vertical axis, and this does not fix the grey vertex.

Now we consider \(C_6\text{.}\)

The cycle \(C_6\) has a distinguishing number of \(2\text{.}\)

A single colour is clearly not sufficient, since \(C_6\) admits both nontrivial rotations and reflections as automorphisms.

To see that two colours are sufficient, observe this colouring:

Since only one of the white vertices has no white neighbours, any automorphism that preserves the colouring must fix that vertex. The only nontrivial automorphism that fixes this vertex is the reflection through the horizontal axis, and that reflection does not preserve the colouring of one of the other two white vertices. Therefore, only the trivial automorphism preserves this colouring.

Before providing some of the known results on distinguishing numbers, we introduce one interesting family of graphs: the hypercubes.

Definition 12.5.8.
The hypercube of dimension \(n\text{,}\) \(Q_n\) has as its vertices all possible binary strings of length \(n\text{.}\) Two vertices are adjacent if the corresponding strings differ in exactly one position.

In Chapter 19 we will look at some of these ideas (binary strings and how many positions they differ in) in more detail. According to the terminology that will be used in that chapter, the vertices of \(Q_n\) are the \(n\)-bit binary strings, and two vertices are adjacent if the corresponding strings have a Hamming distance of \(1\text{.}\)

We can now give distinguishing numbers for some families of graphs.

We mentioned above that almost all graphs have a distinguishing number of \(1\text{.}\) The results we have just listed indicate the pattern that has emerged from research into the distinguishing number of graphs whose distinguishing number is not \(1\text{:}\) that is, in almost all such cases it is possible to find a distinguishing colouring that uses just \(2\) colours.

After doing some work on the distinguishing number herself, Debra Lynn Boutin (1957—) introduced a related concept: the distinguishing cost.

Definition 12.5.10.
For a graph with distinguishing number \(2\text{,}\) the distinguishing cost is the smallest number of vertices that need to be coloured with the less-commonly-used colour, in order to produce a distinguishing colouring of the graph with \(2\) colours (that is, a colouring with \(2\) colours for which only the trivial automorphism preserves the colours).

The distinguishing cost of \(C_6\) is \(3\text{.}\) We have already seen in Example 12.5.7 that using three vertices of each colour can provide a distinguishing colouring. To see that one or two vertices of one colour are not sufficient, we observe that any subset of one or two of the vertices of \(C_6\) is preserved (as a set) by some reflection automorphism. Thus, no matter which one or two vertices we might choose to colour with the second colour, there would be a nontrivial automorphism preserving the colouring.

In fact, the distinguishing cost of \(C_n\) is \(3\) for every \(n \ge 6\text{,}\) by similar reasoning.

In \(2008\text{,}\) Boutin found the following bounds on the distinguishing cost of \(Q_n\text{:}\)

In case you are unfamiliar with this notation, \(\lceil r\rceil\) denotes the ceiling of the real number \(r\text{:}\) the smallest integer that is greater than or equal to \(r\text{.}\)

Since \(\log_2(16)=4\text{,}\) we have
\begin{equation*} \lceil \log_2(16)\rceil +1=4+1=5 \end{equation*}
and
\begin{equation*} 2\lceil\log_2(n)\rceil-1=2(4)-1=7, \end{equation*}
so \(5 \le dc(Q_{16}) \le 7\text{.}\)

While distinguishing is a fascinating topic by itself, we wish to introduce one other family of graphs that relates to automorphisms. We will not provide nearly as much detail on this topic.

In \(1989\text{,}\) Cheryl Elisabeth Praeger (1948—) and Ming-Yao Xu (1941—) introduced a family of graphs that has become known as the Praeger-Xu graphs. This is a family of graphs for which every vertex in each of the graphs has valency \(4\text{.}\) Without going into detail, each of the graphs in the Praeger-Xu family has far more automorphisms (relative to the number of vertices that it has) than any other graph for which every vertex has valency \(4\text{.}\) The Praeger-Xu graphs have been studied by a number of researchers, and have arisen in several contexts related to automorphisms of graphs. In the same paper, Praeger and Xu actually introduced a collection of related families of graphs where every vertex of every graph in a given family has valency \(2p\) for some prime \(p\text{,}\) but the case where \(p=2\) is particularly interesting and this is the family that is known as the Praeger-Xu graphs.

Definition 12.5.14.

The Praeger-Xu graph \(PX(n,k)\) has for its vertices the ordered pairs \((i,x)\text{,}\) where \(i \in \{0, \ldots, n-1\}\) and \(x\) is a binary string of length \(k\text{.}\) Edges are any pair of vertices of the form \(\{(i,ay),(i+1,yb)\}\) where \(y\) is a binary string of length \(k-1\text{,}\) \(a,b \in \{0,1\}\text{,}\) \(i \in \{0, \ldots, n-1\}\text{,}\) and addition in the first entry is performed modulo \(n\text{.}\)

In \(PX(8,5)\text{,}\) the vertex \((7,10111)\) has four neighbours: \((0,01110)\text{,}\) \((0,01111)\text{,}\) \((6,01011)\text{,}\) and \((6,11011)\text{.}\)

The graph \(PX(6,3)\) can be drawn as follows.

The sets of vertices forming a line represent fixed values of the first coordinate, increasing in a clockwise direction. From outside to inside, the second entries of each vertex label are

\begin{equation*} 000,001,010,011,100,101,110,111. \end{equation*}