<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
Generalized de Bruijn Cycles
Joshua N. Cooper1 and Ronald L. Graham2
1Department of Mathematics, Courant Institute of Mathematical Sciences, New York University, NY 10012, USA
2Department of Computer Science and Engineering, University of California at San Diego, CA 92093, USA
Annals of Combinatorics 8 (1) p.13-25 March, 2004
AMS Subject Classification: 94A55, 05C70
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 qn 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.
Keywords: de Bruijn cycle, graph decomposition, probabilistic method


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.