Abstract
In this paper, we investigate the existence of a hamiltonian circuit in the cartesian product of two Cayley digraphs. Three of our results can be summarized as follows. Suppose K is the Cayley digraph of a dihedral, semidihedral, or dicyclic group arising from a specified pair of (standard) generators, and suppose L is a Cayley digraph with a hamiltonian circuit. Then, the cartesian product of K and L has a hamiltonian circuit. As a corollary to our main theorem, we also show that the cartesian product of an undirected cycle of length n and a directed cycle of length k has a hamiltonian circuit unless n = 2 and k is odd. Some open problems are stated.
Original language | English (US) |
---|---|
Pages (from-to) | 297-307 |
Number of pages | 11 |
Journal | Discrete Mathematics |
Volume | 43 |
Issue number | 2-3 |
DOIs | |
State | Published - 1983 |
Bibliographical note
Funding Information:One of the authors( G.L.) did her work at the Universityo f MinnesotaD, uluth, while in an UndergraduatRe esearchP articipationp rogramf undedb y the National ScienceF oundation( Grant NumberN SF/SPI-7926564).