Coloring directed wheel graph $W_6$ with $k$ colors

177 Views Asked by At

Let consider directed wheel graph $G_6$ example. We want to color each vertex on $1$ of $k$ colors. How many different coloring there are if two graphs we consider as the same if one can be transformed into second with some isomorphism that maintains the orientation of the edges and the colors of the vertices?

Solution

Let consider group $\mathbb Z_2 \times \mathbb Z_6$ Elements from first part informs us if we do mirror reflection or not. Elements from second group informs us if we rotate our wheel and how many times. For example $(1,4)$ means that we do mirror reflection and rotate elements $4$ times to right. Ok, now let make cycle index

$$\begin{array}{|c|c|c|c|} \hline elements& cycles\\ \hline (0,0) & x_1^7 \\ \hline (0,0) & x_1 x_6 \\ \hline (0,0) & x_1 x_3^2 ? \\ \hline (0,0) & x_1 x_2^3 \\ \hline (0,0) & x_3^2 x_1 \\ \hline (0,0) & x_1 x_6\\ \hline (1,0) & x_1^7 \\ \hline (1,0) & x_1 x_6 \\ \hline (1,0) & x_1 x_3^2 ? \\ \hline (1,0) & x_1 x_2^3 \\ \hline (1,0) & x_3^2 x_1 \\ \hline (1,0) & x_1 x_6\\ \hline \end{array} $$ $$I(x_1,x_2,x_3,x_4,x_5,x_6,x_7) = \frac{2x_1}{12}(x_1^6 + 2x_6+ 2x_3^2 + x_2^3) $$ so $$I(k,k,k,k,k,k,k) = \frac{k}{6}(k^6 + 2k+ 2k^2 + k^3) $$ is that solution correct?