De Bruijn graph

For a set of m symbols S = {s1, …, sm}, the set of vertices is: If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex.

[2] Much earlier, Camille Flye Sainte-Marie[3] implicitly used their properties.

Binary De Bruijn graphs can be drawn in such a way that they resemble objects from the theory of dynamical systems, such as the Lorenz attractor: This analogy can be made rigorous: the n-dimensional m-symbol De Bruijn graph is a model of the Bernoulli map The Bernoulli map (also called the 2x mod 1 map for m = 2) is an ergodic dynamical system, which can be understood to be a single shift of a m-adic number.

[5] The trajectories of this dynamical system correspond to walks in the De Bruijn graph, where the correspondence is given by mapping each real x in the interval [0,1) to the vertex corresponding to the first n digits in the base-m representation of x. Equivalently, walks in the De Bruijn graph correspond to trajectories in a one-sided subshift of finite type.

Embeddings resembling this one can be used to show that the binary De Bruijn graphs have queue number 2[6] and that they have book thickness at most 5.