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
where \(n = |V(G)|\text{.}\)
Exercises Practice Problems
1.
The complete graph \(K_n\text{,}\) which contains \(n\) vertices with all possible edges.
2.
The cycle \(C_n\text{,}\) consisting of a circle of \(n\) vertices, each connected to its two nearest neighbors.
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.
4.
The path \(P_n\text{,}\) which contains \(n\) vertices connected in a line
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{.}\)
6.
The star \(S_n\text{,}\) consisting of a central vertex connected to \(n-1\) leaf vertices.