Universal cycles of classes of restricted words

DOI10.1016/J.DISC.2010.07.016MaRDI QIDQ712255zbMATHOpenAlexFDO

Authors Arielle Leitner, Anant P. Godbole

Publication date 28 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0808.1309

zbMATH Keywords

passwordde Bruijn digraphuniversal cycleequitable wordgraph connectednessordered Bell number

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10)

Abstract: It is well known that Universal Cycles of $k$-letter words on an $n$-letter alphabet exist for all $k$ and $n$. In this paper, we prove that Universal Cycles exist for restricted classes of words, including: non-bijections, equitable words (under suitable restrictions), ranked permutations, and "passwords".

Recommendations

• Universal cycles of complementary classes
• Universal cycles of restriced words
• Universal cycles for permutations
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• Universal cycles for combinatorial structures

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Generation of Permutations by Adjacent Transposition
• On Universal Cycles for k-Subsets of an n-Set
• Universal Cycles of Discrete Functions
• Universal cycles for combinatorial structures
• Universal cycles of \(k\)-subsets and \(k\)-permutations

Cited in

(12)

• Universal arrays
• Constructing the first (and coolest) fixed-content universal cycle
• Universal cycles of restriced words
• A universal cycle for strings with fixed-content (which are also known as multiset permutations)
• Efficient universal cycle constructions for weak orders
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Universal Cycles for Weight-Range Binary Strings
• Universal cycles of complementary classes
• Cyclic Complexity of Words
• Universal cycles for permutation classes
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set

This page was built for publication: Universal cycles of classes of restricted words

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