Generalized de Bruijn cycles

DOI10.1007/S00026-004-0201-YMaRDI QIDQ1889887zbMATH OpenOpenAlexFDO

Authors Joshua Cooper, Ron Graham

Publication date 13 December 2004

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0402324

zbMATH Keywords

complete directed graphde Bruijn cyclede Bruijn graphgraph decompositionprobabilistic method

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: For a set of integers $I$, we define a $q$-ary $I$-cycle to be a assignment of the symbols 1 through $q$ to the integers modulo $q^n$ so that every word appears on some translate of $I$. 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 $I$. We also prove a variant on recent results concerning decompositions of complete graphs into cycles and employ it to resolve the case of $|I|=2$ completely.

Review text

This paper generalizes the notion of the de Bruijn sequences assumed as \(q\)-ary sequences \(s_0,s_1,\dots,s_{q^n+n-2}\) such that the family \(\{(s_i,s_{i+1},\dots,s_{i+n-1}): i\in\{0,1,\dots,q^n-1\}\}\) consists of all \(q\)-ary sequences of length \(n\). For a given subset \(\mathcal I=\{t_1,t_2,\dots,t_n\}\) of \(\{0,1,\dots,q^n-1\}\) the generalization of a de Bruijn sequence is defined as an \(\mathcal I\)-cycle such that the family \(\{(s_{i+t_1},s_{i+t_2},\dots,s_{i+t_n}): i\in\{0,1,\dots,q^n-1\}\}\) consists of all \(q\)-ary sequences of length \(n\) (with the indices reduced modulo \(q^n+n-1\)). The classical de Bruijn sequences are obtained for \(\mathcal I_d=\{d,d+1,\dots,d+n-1\}\) with \(d\in\{0,1,\dots,q^n-1\}\). The existence of the \(\mathcal I\)-cycles is mainly discussed for the case \(\mathcal I=\{0,d,\dots,(n-1)d\}\), for which the case \(| \mathcal I| =2\) has been solved completely. For the other cases the existence of approximate cycles, that is the shortest sequence that contains all \(q\)-ary sequences of length \(n\) according to \(\mathcal I\), is considered. The paper also contains a number of open problems.

Recommendations

• Contributions to the theory of de Bruijn cycle
• Binary de Bruijn cycles under different equivalence relations
• ``Periods of de Bruijn sequences
• scientific article; zbMATH DE number 1890156
• On the existence of balanced generalized de Bruijn sequences

Cited in

(15)

• On the number of cycles of short length in the de Bruijn-Good graph \(G_ n\)
• Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs
• Binary de Bruijn cycles under different equivalence relations
• Properties of the cycles that contain all vectors of weight k
• s-overlap cycles for permutations
• Shifted de Bruijn graphs
• Generalized de Bruijn digraphs
• scientific article; zbMATH DE number 718858 (Why is no real title available?)
• scientific article; zbMATH DE number 1890156 (Why is no real title available?)
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• Contributions to the theory of de Bruijn cycle
• Overlap cycles for permutations: necessary and sufficient conditions
• On the existence of balanced generalized de Bruijn sequences
• Locating patterns in the de Bruijn torus
• Growing perfect cubes

This page was built for publication: Generalized de Bruijn cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1889887)