Additional Problem 22: Double Helices in de Bruijn Graphs
\(
\def\PD{\mathit{PD}}
\)
A Hamiltonian cycle $C_n$ in the binary de Bruijn graph $G_n$ of
order $n$ is called a double helix if after removing $C_n$
we receive three edge disjoint simple cycles (two of them are
loops).
The corresponding cyclic de Bruijn word is also called a double helix.
Assume you have a primitive polynomial of degree $n$ over $Z_2$.
Construct a de Bruijn binary cyclic word which is a double helix of order $n$.
Use PN (pseudo-noise) sequences of words.
References
-
Terry R. McConnell.
DeBruijn Strings, Double Helices, and the Ehrenfeucht-Mycielski Mechanism.
Report arXiv:1303.6820, 2013.
-
D. Repke and W. Rytter.
On semi-perfect de Bruijn words.
Theor. Comput. Sci., 720:55-63, 2018.