Abstract:

Let $\dC_m$ and~$\dC_n$ be directed cycles of length $m$ and~$n$, with $m,n \ge 3$, and let $P(\dC_m \cartprod \dC_n)$ be the digraph that is obtained from the Cartesian product $\dC_m \cartprod \dC_n$ by choosing a vertex~$v$, and reversing the orientation of all four directed edges that are incident with~$v$. (This operation is called ``pushing'' at the vertex~$v$.) By applying a special case of unpublished work of S.\,X.\,Wu, we find elementary number-theoretic necessary and sufficient conditions for the existence of a hamiltonian cycle in $P(\dC_m \cartprod \dC_n)$. \\ A consequence is that if $P(\dC_m \cartprod \dC_n)$ is hamiltonian, then $\gcd(m,n) = 1$, which implies that $\dC_m \cartprod \dC_n$ is not hamiltonian. This final conclusion verifies a conjecture of J.\,B.\,Klerlein and E.\,C.\,Carr.

Keywords: