On the Hamiltonicity of Directed sigmatau Cayley Graphs (Or: A Tale of
Backtracking)
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Ming Jiang,
Department of Computer Science,
University of Victoria, Canada.
Andrew Weston,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Let tau be the 2cycle (1 2) and sigma the
ncycle (1 2 ... n). These two cycles generate
the symmetric group S_{n}. Let G_{n}
denote the directed Cayley graph
Cay({tau,sigma}:S_{n}).
Based on erroneous computer calculations,
Nijenhuis and Wilf give as an exercise to show
that G_{5} does not have a Hamilton path.
To the contrary, we show that G_{5} is Hamiltonian.
Furthermore, we show that G_{6} has a Hamilton path.
Our results illustrate how a little theory and some good luck
can save a lot of time in backtracking searches.

The postscript file is 185,259 bytes,
the dvi file is 40,416 bytes.

Appeared in Discrete Applied Mathematics,
57 (1995) 7583.

Richard G. Swan, in A Simple Proof of Rankin's Campanological Theorem,
American Mathematical Monthly, 106 (1999) 159161,
has a theorem (see in particular the remark on page 160)
that implies that there is no Hamilton
cycle in G_{n} whenever n is even.
Rankin's original paper is
A campanological problem in group theory,
Proc. Cambridge Philosophical Society, 44 (1948) 1725.

The students Ming Jiang and Andrew Weston are no longer
at the University of Victoria.
Selected other papers that refer to this one:

William Y.C. Chen, Vance Faber, and Emanuel Knill
Restricted Routing and Wide Diameter of the Cycle Prefix Network

Back to list of publications.