×

Universal cycles of classes of restricted words. (English) Zbl 1228.05018

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.

MSC:

05A05 Permutations, words, matrices
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
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.