On existence of an hamiltonian path in cartesian power of directed cycle graph

Question

Is it true, and if so, how to show it, that there is a Hamiltonian path in the cartesian power of a directed cycle graph (i.e. the iterated cartesian/box product $\square$) $C_n^{\square r}$ where $n, r \geq 2$?

I found some articles dealing with this topic, like this one: http://people.uleth.ca/~dave.morris/papers/HPathCartPower.pdf which seems to show a stronger result and is of a very high level for me, which is the characterization of the extremities of the Hamiltonian path according to $n$. Perhaps it is possible from these results to obtain that there is always such a path, but I have the impression (perhaps wrong) that it could exist simpler, as a combinatorial argument.

I'm sorry if it's obvious, but it's not for me as a beginner in graph theory.

Answer 1

If $G$ and $H$ both have a Hamiltonian path starting at any vertex, then the same thing is true of $G \mathbin{\square} H$. From this, we can find a Hamiltonian path in $C_n^{\square r}$ by induction on $r$.

To prove the claim, pick an arbitrary vertex $(v_1,w_1)$ in $G \mathbin{\square} H$. Use our assumption on $G$ and $H$ to find:

• A Hamiltonian path $v_1, v_2, \dots, v_n$ in $G$.
• A sequence of $n$ Hamiltonian paths $P_1, P_2, \dots, P_n$ in $H$, where $P_1$ begins at $w_1$ and $P_i$ begins at the last vertex of $P_{i-1}$ for all $i>1$.

Let $P_i'$ be the path in $G \mathbin{\square} H$ where every vertex of $P_i$ is prefixed by $v_i$. Then concatenating $P_1', P_2', \dots, P_n'$ gives a Hamiltonian path in $G \mathbin{\square} H$ starting at $(v_1, w_1)$.