Joshua N. Cooper^{1} and Ronald L. Graham^{2}

cooper@cims.nyu.edu

graham@ucsd.edu

Annals of Combinatorics 8 (1) p.13-25 March, 2004

Abstract:

For a set of integers , we
define a *q*-ary -cycle to be an assignment of the symbols 1 through *q* to the integers modulo *q*^{n} so that every word appears on some translate of . This definition generalizes that of de Bruijn cycles, and opens up a multitude of questions.
We address the existence of such cycles, discuss "reduced"'
cycles (ones in which the all-zeroes string need not appear), and
provide general bounds on the shortest sequence which contains all
words on some translate of . We also prove a variant on recent results concerning decompositions of complete graphs into
cycles and employ it to resolve the case of = 2 completely.

References:

1. B. Alspach, H. Gavlas, M. Sajna, and H. Verrall, Cycle decompositions IV, Complete directed graphs and fixed length directed cycles, J. Combin. Theory, Ser. A 103 (1) (2003) 165–208.

2. P. Balister, Packing circuits into KN, Combin. Probab. Comput. 10 (6) (2001) 463–499.

3. P. Balister, Packing digraphs with directed closed trails, Combin. Probab. Comput. 12 (1) (2003) 1–15.

4. T.B. Beard Jr., Matrix fields, regular and irregular: a complete fundamental characterization, Linear Algebra Appl. 81 (1986) 137–152.

5. F. Chung and J.N. Cooper, De Bruijn cycles for covering codes, preprint.

6. H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Rev. 24 (2) (1982) 195–221.

7. S. Janson, New versions of Suens correlation inequality, Proceedings of the Eighth International Conference, Random Structures Algorithms 13 (3-4) (1998) 47–483.

8. S.V. Konyagin, I.Z. Rusza, and W. Schlag, On uniformly distributed dilates of finite integer sequences, J. Number Theory 82 (2000) 165–187.

9. R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications 20, Cambridge University Press, Cambridge, 1997.