### 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 |

### Fingerprint

### Cite this

*Discrete Mathematics*,

*43*(2-3), 297-307. https://doi.org/10.1016/0012-365X(83)90166-8

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

Research output: Contribution to journal › Article

*Discrete Mathematics*, vol. 43, no. 2-3, pp. 297-307. https://doi.org/10.1016/0012-365X(83)90166-8

}

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 -