Hamiltonicity after reversing the directed edges at a vertex of a Cartesian product

Abstract

Let ${\vec{C}}_m$ and ${\vec{C}}_n$ be directed cycles of length $m$ and $n$, with $m,n\ge 3$, and let $P({\vec{C}}_m\square {\vec{C}}_n)$ be the digraph that is obtained from the Cartesian product ${\vec{C}}_m\square {\vec{C}}_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({\vec{C}}_m\square {\vec{C}}_n)$. A consequence is that if $P({\vec{C}}_m\square {\vec{C}}_n)$ is hamiltonian, then $\gcd (m,n)=1$, which implies that ${\vec{C}}_m\square {\vec{C}}_n$ is not hamiltonian. This final conclusion verifies a conjecture of J.B.Klerlein and E.C.Carr.

13 pages