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

graph decompositionprobabilistic methodde Bruijn graphde Bruijn cyclecomplete directed graph

Mathematics Subject Classification ID

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

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.

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

(14)

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

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)