Double Eulerian cycles on de Bruijn digraphs

Abstract

A binary de Bruijn sequence has the property that every n-tuple is distinct on a given period of length 2". An efficient algorithm to generate a class of classi- cal de Bruijn sequences is given based upon the distance between cycles within the Good - de Bruijn digraph. The de Bruijn property on binary sequences is shown to be a randomness property of the ZERO and ONE run sequences. Utilizing this randomness we find additional new structure in de Bruijn sequences. We analyze binary sequences that are not de Bruijn but instead possess the sufficient structure so that every distinct binary n-tuple can be systematically "combed" out of the se- quence. These complete or nonclassical de Bruijn sequences are a generalization of the well-known de Bruijn cycle. Our investigation focuses on binary sequences, called double Eulerian cycles, that define a cycle along a graph (digraph) visiting each edge (arc) exactly twice. A new algorithm to generate a class of double Eulerian cycles on graphs and digraphs is found. Double Eulerian cycles along the binary Good - de Bruijn digraph are partitioned by the run structure of their defining sequences. This partition allows for a statistical analysis to determine the relative size of the set of complete cycles defined by the sequences we study. A measure that categorizes double Eulerian cycles along graphs (digraphs) by the distance between the two visitations of each edge (arc) is provided. An algorithm to generate double Eulerian cycles of minimum measure is given.