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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page