CLR cover

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