de Bruijn Graph


A graph whose nodes are sequences of symbols from some alphabet and whose edges indicate the sequences which might overlap. The above figures show the first few n-dimensional de Bruijn graphs on m symbols (m,n) for m,n>=2. The graph (m,n) is implemented in the Wolfram Language as DeBruijnGraph[m, n].

The independence number of the de Bruijn graphs (2,n) for n=1, 2, ... are given by 1, 2, 3, 7, 13, 28, ... (OEIS A006946).

Explore with Wolfram|Alpha


Golomb, S. W. Shift Register Sequences. San Francisco, CA: Holden-Day, 1967.Ralston, A. "de Bruijn Sequences--A Model Example of the Interaction of Discrete Mathematics and Computer Science." Math. Mag. 55, 131-143, 1982.Sloane, N. J. A. Sequence A006946/M0834 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

de Bruijn Graph

Cite this as:

Weisstein, Eric W. "de Bruijn Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications