On hamiltonian circuits in cartesian products of Cayley digraphs

David Witte, Gail Letzter, Joseph A. Gallian

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish (US)
Pages (from-to)297-307
Number of pages11
JournalDiscrete Mathematics
Volume43
Issue number2-3
DOIs
StatePublished - 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).

Fingerprint Dive into the research topics of 'On hamiltonian circuits in cartesian products of Cayley digraphs'. Together they form a unique fingerprint.

Cite this