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

preprint2022arXivOpen access

Abstract

Let C⃗m\vec C_m and C⃗n\vec C_n be directed cycles of length mm and nn, with m,n≥3m,n \ge 3, and let P(C⃗m□C⃗n)P(\vec C_m \mathbin{\Box} \vec C_n) be the digraph that is obtained from the Cartesian product C⃗m□C⃗n\vec C_m \mathbin{\Box} \vec C_n by choosing a vertex vv, and reversing the orientation of all four directed edges that are incident with vv. (This operation is called "pushing" at the vertex vv.) 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(C⃗m□C⃗n)P(\vec C_m \mathbin{\Box} \vec C_n). A consequence is that if P(C⃗m□C⃗n)P(\vec C_m \mathbin{\Box} \vec C_n) is hamiltonian, then gcd⁡(m,n)=1\gcd(m,n) = 1, which implies that C⃗m□C⃗n\vec C_m \mathbin{\Box} \vec C_n is not hamiltonian. This final conclusion verifies a conjecture of J.B.Klerlein and E.C.Carr.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.