##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 406.05048

**Autor: ** Trotter, William T.jun.; Erdös, Paul

**Title: ** When the Cartesian product of directed cycles is Hamiltonian. (In English)

**Source: ** J. Graph Theory 2, 137-142 (1978).

**Review: ** The Cartesian product of two hamiltinian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the cartesian product C_{n1}× C_{n2} of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n_{1} and n_{2} is at least two and there exist positive integers d_{1}, d_{2} so that d_{1}+d_{2} = d and g.c.d. (n_{1},d_{1}) = g.c.d. (n_{2},d_{2}) = 1. We also discuss some number-theoretic problems motivated by this result.

**Classif.: ** * 05C45 Eulerian and Hamiltonian graphs

05C99 Graph theory

11P81 Elementary theory of partitions

**Keywords: ** Cartesian product; Hamiltonian graphs; directed graphs; directed cycles

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag