Equivalence class universal cycles for permutations

DOI10.1016/0012-365X(94)00314-9MaRDI QIDQ1910573zbMATH OpenFDO

Authors Garth Isaak, Glenn H. Hurlbert

Publication date 25 March 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00314-9

zbMATH Keywords

de Bruijn cyclesEulerian cyclepermutationsuniversal cycles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Paths and cycles (05C38) Graph theory (05C99)

Review text

The paper sets out to construct a complete family of universal cycles of \(n\)-permutations using \(n+ 1\) symbols, and an equivalence relation based on differences. The notion of universal cycles as cyclic representations of combinatorial objects, a generalization of de Bruijn cycles, is of recent (1990's) interest---and the universal cycles for permutations examined in this paper is an example of this. Having set up the equivalence classes, the authors then construct a directed graph---which proves to be Eulerian. An Eulerian cycle provides the desired universal cycle for their example.

Recommendations

• Universal cycles for permutations
• Universal cycles for combinatorial structures
• Universal cycles of k-subsets and k-permutations

Cites work

• scientific article; zbMATH DE number 3993640 (Why is no real title available?)
• Universal cycles for combinatorial structures
• Universal cycles of k-subsets and k-permutations

Cited in

(7)

• Shorthand universal cycles for permutations
• Shortened universal cycles for permutations
• Enumerations of universal cycles for \(k\)-permutations
• Equivalence classes of permutations modulo excedances
• Designing preference functions for de Bruijn sequences with forbidden words
• On a greedy algorithm to construct universal cycles for permutations
• Graph universal cycles: compression and connections to universal cycles

This page was built for publication: Equivalence class universal cycles for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1910573)