An explicit universal cycle for the (n-1)-permutations of an n-set

2007/10/09 by Frank Ruskey, Ruskey, Frank, Aaron Williams +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0710.1842

openalex publication_date 2007/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show how to construct an explicit Hamilton cycle in the directed Cayley graph Cay(σ_n, sigma_n-1 : \mathbbS_n), where σ_k = (1 2 >... k). The existence of such cycles was shown by Jackson (Discrete Mathematics, 149 (1996) 123-129) but the proof only shows that a certain directed graph is Eulerian, and Knuth (Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)) asks for an explicit construction. We show that a simple recursion describes our Hamilton cycle and that the cycle can be generated by an iterative algorithm that uses O(n) space. Moreover, the algorithm produces each successive edge of the cycle in constant time; such algorithms are said to be loopless.

Cited by

• Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random

Related

• On a Greedy Algorithm to Construct Universal Cycles for Permutations
• Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)
• From cycles to circles in Cayley graphs
• A Simple Proof of the Cayley Formula using Random Graphs
• Cayley graphs of order 16p are hamiltonian