Hamiltonicity after reversing the directed edges at a vertex of a Cartesian product
DOI:
https://doi.org/10.13069/jacodesmath.v10i1.246Keywords:
Hamiltonian cycle, Cartesian product, Directed cycle, Pushing at a vertex, Reverse edgesAbstract
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 2022Downloads
References
S. J. Curran, M. N. Ferencak, C. J. Morgan, and J. W. Thompson, The hamiltonicity of a Cayley digraph of a modified abelian group on two generators, Congr. Numer. 188 (2007) 75–95.
S. J. Curran and D. Witte, Hamilton paths in Cartesian products of directed cycles, in: B. R. Alspach and C. D. Godsil (Eds.), Cycles in Graphs, North-Holland Mathematics Studies, Vol. 115, North-Holland, Amsterdam, 1985, pp. 35–74.
J. Gallian, Contemporary Abstract Algebra, 10th ed., CRC Press, Boca Raton, FL, 2021.
R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, FL, 2011.
S. Housman, Enumeration of Hamiltonian paths in Cayley diagrams, Aequationes Math. 23(1) (1981) 80–97.
J. B. Klerlein and E. C. Carr, Hamiltonicity in $C_n \times C_m$ after a single push, Congr. Numer. 190 (2008) 87–96.
W. F. Klostermeyer, Pushing vertices and orienting edges, Ars Combin. 51 (1999) 65–75.
R. Rankin, A campanological problem in group theory, Proc. Cambridge Philos. Soc. 44(1) (1948) 17–25.
Wikipedia, Vertex cycle cover, 2022, https://en.wikipedia.org/wiki/Vertex_cycle_cover.
D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51(3) (1984) 293–304.
S. X. Wu, Cycles in the Cartesian product of two directed cycles, presented at Joint Mathematics Meetings (JMM 2007), New Orleans, LA, 2007 (unpublished).
