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.

Received: 9 April 2022 | Accepted: 9 July 2022