De Bruijn graph

In graph theory, an $n$ -dimensional De Bruijn graph of $m$ symbols is a directed graph representing overlaps between sequences of symbols. It has $m n$ vertices, consisting of all possible length- $n$ sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of $m$ symbols $S = {s 1, \dots, s m},$ the set of vertices is:

V=S^{n}=\{(s_{1},\dots ,s_{1},s_{1}),(s_{1},\dots ,s_{1},s_{2}),\dots ,(s_{1},\dots ,s_{1},s_{m}),(s_{1},\dots ,s_{2},s_{1}),\dots ,(s_{m},\dots ,s_{m},s_{m})\}.

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. Thus the set of arcs (that is, directed edges) is

E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_{i}\in S,1\leq i\leq n,1\leq j\leq m\}.

Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were invented independently by both de Bruijn^[1] and I. J. Good.^[2] Much earlier, Camille Flye Sainte-Marie^[3] implicitly used their properties.

^ Cite error: The named reference Bruijn1946 was invoked but never defined (see the help page).
^ Cite error: The named reference Good1946 was invoked but never defined (see the help page).
^ Cite error: The named reference Flye1894 was invoked but never defined (see the help page).

[Bruijn1946-1] Cite error: The named reference Bruijn1946 was invoked but never defined (see the help page).

[Good1946-2] Cite error: The named reference Good1946 was invoked but never defined (see the help page).

[Flye1894-3] Cite error: The named reference Flye1894 was invoked but never defined (see the help page).

[1]

[2]

[3]