Premium
When the cartesian product of directed cycles is Hamiltonian
Author(s) -
Trotter William T.,
Erdös Paul
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020206
Subject(s) - cartesian product , mathematics , hamiltonian (control theory) , combinatorics , cartesian coordinate system , hamiltonian path , discrete mathematics , graph , geometry , mathematical optimization
The cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the cartesian product C n 1 × C n 2 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.