Constructing de Bruijn sequences by concatenating smaller universal cycles

Abstract

We present sufficient conditions for when an ordering of universal cycles ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_m$ for disjoint sets ${\mathbf{S}}_1,{\mathbf{S}}_2,\dots ,{\mathbf{S}}_m$ can be concatenated together to obtain a universal cycle for $\mathbf{S}={\mathbf{S}}_1\cup {\mathbf{S}}_2\cup \cdots \cup {\mathbf{S}}_m$. When $\mathbf{S}$ is the set of all $k$-ary strings of length $n$, the result of such a successful construction is a de Bruijn sequence. Our conditions are applied to generalize two previously known de Bruijn sequence constructions and then they are applied to develop three new de Bruijn sequence constructions.