Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)

Abstract

The symmetric group is generated by σ = (1 2 ... n) and τ = (1 2). We answer an open problem of Nijenhuis and Wilf by constructing a Hamilton path in the directed Cayley graph for all n, and a Hamilton cycle for odd n.

Small typo corrected in Definition 1