Cayley Digraphs of Groups

Find a Hamiltonian circuit in the digraph given in Example 7 different from the one in Figure 28.3.

Find a Hamiltonian circuit in

Find a Hamiltonian circuit in

where $m$ is even.

Write the sequence of generators for each of the circuits found in Exercises 1, 2, and 3.

Use the Cayley digraph in Example 7 to evaluate the product $a^3ba^{-1}ba^3b^{-1}$.

Let $x$ and $y$ be two vertices of a Cayley digraph. Explain why two paths from $x$ to $y$ in the digraph yield a group relation--- that is, an equation of the form $a_1a_2 \cdots a_m = b_1b_2 \cdots b_n$, where the $a_i$'s and $b_j$'s are generators of the Cayley digraph.

Use the Cayley digraph in Example 7 to verify the relation $aba^{-1}b^{-1}a^{-1}b^{-1} = a^2ba^3$.

Identify the following Cayley digraph of a familiar group.

Let $D_4 = \langle r, f \mid r^4 = e = f^2, rf = fr^{-1} \rangle$. Verify that

is a Hamiltonian circuit in

Draw a picture of $\mathrm{Cay}(\left\{ 2, 5\right\} : Z_8)$.

If $s_1, s_2, \ldots , s_n$ is a sequence of generators that determines a Hamiltonian circuit beginning at some vertex, explain why the same sequence determines a Hamiltonian circuit beginning at any point. (This exercise is referred to in this chapter.)

Show that the Cayley digraph given in Example 7 has a Hamiltonian path from $e$ to $a$.

Show that there is no Hamiltonian path in

from $(0, 0)$ to $(2, 0)$.

Draw $\mathrm{Cay}(\left\{ 2, 3\right\} : Z_6)$. Is there a Hamiltonian circuit in this digraph?

Let $D_4 = \langle a, b \mid a^2 = b^2 = (ab)^4 = e \rangle$. Draw $\mathrm{Cay}(\left\{ a, b\right\} : D_4)$. Why is it reasonable to say that this digraph is undirected?

Let $D_n$ be as in Example 10. Show that $2 * [(n - 1) * r, f]$ is a Hamiltonian circuit in $\mathrm{Cay}(\left\{ r, f\right\} : D_n)$.

Let $Q_8 = \langle a, b \mid a^8 = e, a^4 = b^2, b^{-1}ab = a^{-1} \rangle$. Find a Hamiltonian circuit in $\mathrm{Cay}(\left\{ a, b\right\} : Q_8)$.

Let $Q_8$ be as in Exercise 18. Find a Hamiltonian circuit in

Prove that the Cayley digraph given in Example 6 does not have a Hamiltonian circuit. Does it have a Hamiltonian path?

Find a Hamiltonian circuit in

Does this circuit generalize to the case $D_{n+1} \oplus Z_n$ for all $n \ge 3$?

Let $Q_8$ be as in Exercise 18. Find a Hamiltonian circuit in

Let $Q_4$ be as in Example 7. Find a Hamiltonian circuit in

Let $Q_4$ be as in Example 7. Find a Hamiltonian circuit in

Write the sequence of generators that describes the Hamiltonian circuit in Example 9.

Let $D_n$ be as in Example 10. Find a Hamiltonian circuit in

Does your circuit generalize to the case $D_n \oplus Z_{n+1}$ for all $n \ge 4$?

Prove that $\mathrm{Cay}(\left\{ (0, 1), (1, 1)\right\} : Z_m \oplus Z_n)$ has a Hamiltonian circuit for all $m$ and $n$ greater than 1.

Suppose that a Hamiltonian circuit exists for $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_m \oplus Z_n)$ and that this circuit exits from vertex $(a, b)$ vertically. Show that the circuit exits from every member of the coset $(a, b) + \langle (1, -1) \rangle$ vertically.

Let $D_2 = \langle r, f \mid r^2 = f^2 = e, rf = fr^{-1} \rangle$. Find a Hamiltonian circuit in $\mathrm{Cay}(\left\{ (r, 0), (f, 0), (e, 1)\right\} : D_2 \oplus Z_3)$.

Let $Q_8$ be as in Exercise 18. Find a Hamiltonian circuit in $\mathrm{Cay}(\left\{ (a, 0), (b, 0), (e, 1)\right\} : Q_8 \oplus Z_3)$.

In $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_4 \oplus Z_5)$, find a sequence of generators that visits exactly one vertex twice and all others exactly once and returns to the starting vertex.

In $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_4 \oplus Z_5)$, find a sequence of generators that visits exactly two vertices twice and all others exactly once and returns to the starting vertex.

Find a Hamiltonian circuit in $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_4 \oplus Z_6)$.

Let $G$ be the digraph obtained from $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_3 \oplus Z_5)$ by deleting the vertex $(0, 0)$. Prove that $G$ has a Hamiltonian circuit.

Prove that the digraph obtained from $\mathrm{Cay}(\left\{ (1, 0), (0, 1)\right\} : Z_4 \oplus Z_7)$ by deleting the vertex $(0, 0)$ has a Hamiltonian circuit.

Let $G$ be a finite group generated by $a$ and $b$. Let $s_1, s_2, \ldots , s_n$ be the arcs of a Hamiltonian circuit in the digraph $\mathrm{Cay}(\left\{ a, b\right\} : G)$. We say that the vertex $s_1s_2 \cdots s_i$ travels by $a$ if $s_{i+1} = a$. Show that if a vertex $x$ travels by $a$, then every vertex in the coset $x\langle ab^{-1} \rangle$ travels by $a$.

A finite group is called Hamiltonian if all of its subgroups are normal. (One non-Abelian example is $Q_4$.) Show that Theorem 28.3 can be generalized to include all Hamiltonian groups.