Combi Graph Automorphisms and Graph Labelings

Chapter 24 Graph Automorphisms and Graph Labelings

For each graph \(G\text{,}\) determine either

\(\bullet \,\,\, |\mathrm{Aut}(G)|\text{,}\) the number of the automorphisms of \(G\text{,}\) or

\(\bullet \,\,\, \ell(G)\text{,}\) the number of distinct labelings of \(G\text{.}\)

Explain how you found this number. Once you have determined one of these numbers, you can find the other using the formula

\begin{equation*} |\mathrm{Aut}(G)| \cdot \ell(G) = n! \end{equation*}

where \(n = |V(G)|\text{.}\)

Exercises Practice Problems

1.

The complete graph \(K_n\text{,}\) which contains \(n\) vertices with all possible edges. Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(K_n)| &=& n! \\ \ell(K_n)&=& 1 \\ |\mathrm{Aut}(K_n)| \cdot \ell(K_n)&=& n! \end{array} \end{equation*}

We explain why \(\ell(K_n)=1\text{.}\) All labelings of \(K_n\) are the same: every vertex is the same as every other vertex.

2.

The cycle \(C_n\text{,}\) consisting of a circle of \(n\) vertices, each connected to its two nearest neighbors. Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(C_n)| &=& 2n \\ \ell(C_n)&=&\frac{(n-1)!}{2} \\ |\mathrm{Aut}(C_n)| \cdot \ell(C_n)&=&n! \end{array} \end{equation*}

We explain why \(\mathrm{Aut}(C_n)=2n\text{.}\) The cycle has a rotational symmetry of order \(n\text{.}\) We can also reverse the order of these labels (from clockwise to counterclockwise). This doubles the number of equivalent labels, for a total of \(2n\text{.}\)

3.

The wheel \(W_n\text{,}\) consisting of a circle of \(n-1\) vertices, each connected to its two nearest neighbors, along with an \(n\)th hub vertex, which is connected to all other vertices. Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(W_n)| &=& \displaystyle{2(n-1)} \\ \ell(W_n)&=& \frac{n!}{2(n-1)} = n \cdot \frac{(n-2)!}{2} \\ |\mathrm{Aut}(W_n)| \cdot \ell(W_n)&=& n! \end{array} \end{equation*}

We explain why \(\ell(W_n)=n \cdot \frac{(n-2)!}{2}\text{.}\) First, we label the hub vertex, which can be done in \(n\) ways. Next, we label the remaining \(n-1\) vertices along the rim of the wheel using the other \(n-1\) elements. By the previous problem, the number of ways to do that is \(\frac{(n-2)!}{2}\text{.}\) By the product principle, the total number of ways to label is \(n \cdot \frac{(n-2)!}{2}\text{.}\)

4.

The path \(P_n\text{,}\) which contains \(n\) vertices connected in a line Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(P_n)| &=& 2 \\ \ell(P_n)&=& \frac{n!}{2} \\ |\mathrm{Aut}(P_n)| \cdot \ell(P_n)&=&n! \end{array} \end{equation*}

We explain why \(|\mathrm{Aut}(P_n)|=2\text{.}\) There is only one non-trivial symmetry for the path: a mirror symmetry about its center.

5.

The complete bipartite graph \(K_{m,n}\text{,}\) where \(m \neq n\text{,}\) consisting of a set \(U\) of \(m\) vertices and a set \(W\) of \(n\) vertices, with edges between every pair \(u \in U\) and \(v \in V\text{.}\) Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(K_{n,m})| &=& n! \, m! \\ \ell(K_{n,m}) &=& { n+m \choose n} = \frac{(n+m)!}{n! \, m!} \\ |\mathrm{Aut}(K_{n,m})| \cdot \ell(K_{n,m}) &=& (n+m)! \end{array} \end{equation*}

We explain why \(|\mathrm{Aut}(K_{n,m})|=n! \, m!\text{.}\) Permuting the labels of \(U\) does not change the actual label of the graph. Likewise, permuting the labels of \(W\) doesn't change the graph labeling. By the product principle, the number of automorphisms is \(n! \, m!\text{.}\)

6.

The star \(S_n\text{,}\) consisting of a central vertex connected to \(n-1\) leaf vertices. Solution.

\begin{equation*} \begin{array}{rcl} |\mathrm{Aut}(S_n)| &=& (n-1)! \\ \ell(S_n)&=&n \\ |\mathrm{Aut}(S_n)| \cdot \ell(S_n) &=& n! \end{array} \end{equation*}

We explain why \(\ell(S_n)=n\text{.}\) First, we pick a label for the central node, which can be done in \(n\) ways. The remaining labels do not matter.