On hamiltonian circuits in cartesian products of Cayley digraphs

David Witte, Gail Letzter, Joseph A Gallian

Research output: Contribution to journalArticle

6 Citations (Scopus)

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

Fingerprint

Cayley Digraph
Hamiltonians
Hamiltonian circuit
Cartesian product
Networks (circuits)
Cycle
Open Problems
Corollary
Odd
Generator
Theorem

Cite this

On hamiltonian circuits in cartesian products of Cayley digraphs. / Witte, David; Letzter, Gail; Gallian, Joseph A.

In: Discrete Mathematics, Vol. 43, No. 2-3, 1983, p. 297-307.

Research output: Contribution to journalArticle

Witte, David ; Letzter, Gail ; Gallian, Joseph A. / On hamiltonian circuits in cartesian products of Cayley digraphs. In: Discrete Mathematics. 1983 ; Vol. 43, No. 2-3. pp. 297-307.
@article{eb820973ba0a43b1a72ab6b95125cb21,
title = "On hamiltonian circuits in cartesian products of Cayley digraphs",
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.",
author = "David Witte and Gail Letzter and Gallian, {Joseph A}",
year = "1983",
doi = "10.1016/0012-365X(83)90166-8",
language = "English (US)",
volume = "43",
pages = "297--307",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "2-3",

}

TY - JOUR

T1 - On hamiltonian circuits in cartesian products of Cayley digraphs

AU - Witte, David

AU - Letzter, Gail

AU - Gallian, Joseph A

PY - 1983

Y1 - 1983

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

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

UR - http://www.scopus.com/inward/record.url?scp=49049127458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49049127458&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(83)90166-8

DO - 10.1016/0012-365X(83)90166-8

M3 - Article

AN - SCOPUS:49049127458

VL - 43

SP - 297

EP - 307

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2-3

ER -