Euler Cycle  Output  

Given an alphabet of size $k$, the de Bruijn graph of order $n$ is the directed graph $G(n,k) = (V,E)$ where $V$ is the set of all $k$ary strings of length $n$ and there is a directed edge $e=(u,v)$ from $u = u_1u_2\cdots u_n$ to $v=v_1v_2\cdots v_n$ if $u_2\cdots u_n = v_1\cdots v_{n1}$. Each edge $e$ is labeled by $v_n$. Outputting the edge labels in a Hamilton cycle of $G(n,k)$ produces a DB sequence. Below (left) is a Hamilton cycle in the de Bruijn graph $G(3,2)$. Starting from 000, its corresponding DB sequence is 10111000.
Each de Bruijn graph is connected and the indegree and the outdegree of each vertex is $k$; the graph $G(n,k)$ is Eulerian. $G(n,k)$ is the line graph of $G(n{}1,k)$ which means an Euler cycle in $G(n{}1,k)$ corresponds to a Hamilton cycle in $G(n,k)$. Thus, the sequence of edge labels visited in an Euler cycle is a DB sequence. Illustrated above (right) is an Euler cycle in $G(3,2)$. The corresponding DB sequence is 0111101011001000.
Finding an Euler cycle in an Eulerian graph is lineartime solvable with respect to the size of the graph. Such an algorithm is given below. However, since the graph must be stored, applying such an algorithm to find a DB sequence requires exponential $O(k^n)$ space. As noted below, the following Euler cycle algorithm can be related to the greedy constructions.
Finding an Euler cycle
The following algorithm for finding an Euler cycle is based on Fleury [Fle83] with details taken from [Rus03]. The basic idea is do not burn bridges. In other words, do not visit (and use up) an edge if it leaves the remaining graph disconnected.
 Pick a root vertex and compute a spanning intree $T$
 Make each edge of $T$ (the bridges) the last edge on the adjacency list of the corresponding vertex
 Starting from the root, traverse edges in a DFS manner by visiting the first unused edge in the current vertex's adjacency list
A second wellknown Euler cycle algorithm is from Hierholzer [Hie73]:
 Start at an arbitrary vertex $v$ visiting edges in a depthfirst manner until returning to $v$
 Repeat until all edges are visited: Start from any vertex $u$ on the current cycle and visit remaining edges in a DFS manner until returning to $u$. Join the two cycles together.
This cyclejoining approach is the basis for all the binary shift rule constructions.
Greedy algorithms, preference tables, and Euler cycles
Preference tables [Alh12] (also called lookup tables [Xie87]) generalize the notion of the greedy constructions. In particular, a preference table specifies the precise order that the edges are visited for each vertex when performing Step 3 in Fleury's Euler cycle algorithm. Thus given a preference table and a root vertex, Step 3 in the algorithm can be applied to construct a DB sequence if combining the last edge from each nonroot vertex forms a spanning intree to the root. For example, the preference tables and corresponding spanning intrees for the Preferlargest, Prefersame, and Preferopposite constructions are given below for $G(3,2)$. For the Preferlargest, the only valid root is 000. For the Prefersame, either 010 or 101 could be chosen as root. The Preferopposite has a small nuance. By its strict definition, the edges will not create a spanning intree for any root. But by changing the preference for the single string 111, a spanning intree is created when rooted at 000.
 [Alh12] A. Alhakim. Spans of preference functions for de Bruijn sequences. Discrete Appl. Math., 160(78):992–998, 2012.
 [Fle83] Fleury. Deux problemes de geometrie de situation. Journal de mathematiques elementaires, 42:257–261, 1883.
 [Hie73] C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6:30–32, 1873.
 [Rus03] F. Ruskey. Combinatorial generation. Working Version (1jCSC 425/520), 2003.
 [Xie87] S. Xie. Notes on de Bruijn sequences. Discrete Appl. Math., 16(2):157177, 1987.