THE HAMILTONICITY OF DIRECTED SIGMA-TAU-CAYLEY GRAPHS (OR-A TALE OF BACKTRACKING)

Let tau be the 2-cycle (1 2) and sigma the n-cycle (1 2 ... n). These two cycles generate the symmetric group S(n). Let G(n) denote the dire cted Cayley graph Cay({tau, sigma}: S(n)). Based on erroneous computer calculations, Nijenhuis and Wilf (1975, p. 238; 1978, p. 288) give as an exercise to show that G5 does not have a Hamiltonian path. To the contrary, we show that G5 is Hamiltonian. Furthermore, we show that G6 has a Hamiltonian path. Our results illustrate how a little theory an d some good luck can save a lot of time in backtracking searches.