On the Hamiltonicity of Directed sigma-tau 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 2-cycle (1 2) and sigma the
n-cycle (1 2 ... n). These two cycles generate
the symmetric group Sn. Let Gn
denote the directed Cayley graph
Cay({tau,sigma}:Sn).
Based on erroneous computer calculations,
Nijenhuis and Wilf give as an exercise to show
that G5 does not have a Hamilton path.
To the contrary, we show that G5 is Hamiltonian.
Furthermore, we show that G6 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) 75-83.
-
Richard G. Swan, in A Simple Proof of Rankin's Campanological Theorem,
American Mathematical Monthly, 106 (1999) 159-161,
has a theorem (see in particular the remark on page 160)
that implies that there is no Hamilton
cycle in Gn whenever n is even.
Rankin's original paper is
A campanological problem in group theory,
Proc. Cambridge Philosophical Society, 44 (1948) 17-25.
-
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.