When the cartesian product of directed cycles is Hamiltonian

Publisher Website
Google Scholar
Abstract
The cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the cartesian product Cn1 × Cn2 of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n1 and n2 is at least two and there exist positive integers d1, d2 so that d1 + d2 = d and g.c.d. (n1, d1) = g.c.d. (n2, d2) = 1. We also discuss some number‐theoretic problems motivated by this result.

This publication has 2 references indexed in Scilit: