Sách On Universal Cycles of Labeled Graphs

1 Introduction
A simple example of a universal cycle (U-cycle) is the cyclic string 11101000, which
contains every 3-letter word on a binary alphabet precisely once. We obtain these words
by taking substrings of length 3; it is useful to imagine that we are looking at the string
through a “window” of length 3, and we shift the window to transition from one word to
the next, allowing the window to wrap if necessary.
Universal cycles have been shown to exist for words of any length and for any alphabet
size. (For the special case of a binary alphabet, such strings are also known as de Bruijn
cycles). The concept easily lends itself to extension, and universal cycles for permutations,
partitions, and certain classes of functions are well-studied in the literature (see Chung,
Diaconis, Graham [1] for an overview of previous work in the field). In all cases, the
distinguishing feature of a universal cycle is that by shifting a window through a cyclic