Universal Cycles of Restricted Classes of Words

Preprint English OPEN
Leitner, Arielle; Godbole, Anant;
  • Subject: 05B99 | Mathematics - Combinatorics
    arxiv: Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) | Mathematics::Combinatorics | Computer Science::Formal Languages and Automata Theory

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),... View more
  • References (7)

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

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

  • Related Organizations (1)
  • Metrics
Share - Bookmark