publication . Preprint . 2008

Universal Cycles of Restricted Classes of Words

Leitner, Arielle; Godbole, Anant;
Open Access English
  • Published: 08 Aug 2008
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".
arXiv: Computer Science::Formal Languages and Automata TheoryMathematics::CombinatoricsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
free text keywords: Mathematics - Combinatorics, 05B99
Related Organizations
Funded by
NSF| REU Site: Probability and Discrete Mathematics
  • Funder: National Science Foundation (NSF)
  • Project Code: 0552730
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
Download from

[1] A. Bechel, B. LaBounty-Lay and A. Godbole (2008), “Universal cycles of discrete functions,” Congressus Numerantium 189, 121-128.

[2] F. Chung, P. Diaconis, and R. Graham (1992), “Universal Cycles for combinatorial structures,” Discrete Math. 110, 43-59.

[3] G. Hurlbert (1994), “On universal cycles for k-subsets of an n-element set,” SIAM J. Discrete Math. 7, 598-604. [OpenAIRE]

[4] B. Jackson (1993), “Universal cycles of k-subsets and k-permutations,” Discrete Math. 117, 114-150.

[5] D. Knuth (2005), The Art of Computer Programming, Volume 4, Fascicle 2, Pearson, NJ.

[6] F. Ruskey and A. Williams (2008), “An explicit universal cycle for the n − 1-permutations of an n-set,” Talk at Napier Workshop.

[7] D. West (1996), Introduction to Graph Theory, Prentice Hall, New Jersey.

Any information missing or wrong?Report an Issue