Universal cycles of classes of restricted words

DOI10.1016/J.DISC.2010.07.016zbMATH Open1228.05018arXiv0808.1309OpenAlexW2033624808MaRDI QIDQ712255FDOQ712255

Anant P. Godbole, Arielle Leitner

Publication date: 28 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

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".

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal cycles for combinatorial structures
• On Universal Cycles for k-Subsets of an n-Set
• Generation of Permutations by Adjacent Transposition
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• An explicit universal cycle for the ( n -1)-permutations of an n -set
• Universal Cycles of Discrete Functions

Cited In (8)

• A universal cycle for strings with fixed-content (which are also known as multiset permutations)
• 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
• Constructing the first (and coolest) fixed-content universal cycle
• Cyclic Complexity of Words
• Universal Cycles for Weight-Range Binary Strings
• Efficient universal cycle constructions for weak orders
• 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)