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 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.
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