Leitner, Arielle; Godbole, Anant Universal cycles of classes of restricted words. (English) Zbl 1228.05018 Discrete Math. 310, No. 23, 3303-3309 (2010). Summary: It is well known that Universal cycles (U-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 several restricted classes of words, including non-bijections, “equitable” words (under suitable restrictions), ranked permutations, and “passwords”. In each case, proving the connectedness of the underlying de Bruijn digraph is a non-trivial step. Cited in 6 Documents MSC: 05A05 Permutations, words, matrices 05C20 Directed graphs (digraphs), tournaments 68R10 Graph theory (including graph drawing) in computer science Keywords:universal cycle; de Bruijn digraph; graph connectedness; equitable word; ordered Bell number; password PDFBibTeX XMLCite \textit{A. Leitner} and \textit{A. Godbole}, Discrete Math. 310, No. 23, 3303--3309 (2010; Zbl 1228.05018) Full Text: DOI arXiv References: [1] Bechel, A.; LaBounty-Lay, B.; Godbole, A., Universal cycles of discrete functions, Congr. Numer., 189, 121-128 (2008) · Zbl 1163.05020 [2] Chung, F.; Diaconis, P.; Graham, R., Universal cycles for combinatorial structures, Discrete Math., 110, 43-59 (1992) · Zbl 0776.05001 [3] Ohad Feldheim, Personal communication.; Ohad Feldheim, Personal communication. [4] Hurlbert, G., On universal cycles for \(k\)-subsets of an \(n\)-element set, SIAM J. Discrete Math., 7, 598-604 (1994) · Zbl 0810.05012 [5] Jackson, B., Universal cycles of \(k\)-subsets and \(k\)-permutations, Discrete Math., 117, 114-150 (1993) · Zbl 0783.05001 [6] Johnson, S. M., Generation of permutations by adjacent transposition, Math. Comput., 17, 282-285 (1963) · Zbl 0114.01203 [7] Knuth, D., The Art of Computer Programming, Volume 4, Fascicle 2 (2005), Pearson: Pearson NJ · Zbl 1127.68068 [8] F. Ruskey, A. Williams, An explicit universal cycle for the \(n - 1n\); F. Ruskey, A. Williams, An explicit universal cycle for the \(n - 1n\) · Zbl 1300.05305 [9] (Stevens, B.; Hurlbert, G.; Jackson, B., Discrete Mathematics, vol. 309 (2009)), (special issue) [10] West, D., Introduction to Graph Theory (1996), Prentice Hall: Prentice Hall New Jersey · Zbl 0845.05001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.