DeBruijnGraph

DeBruijnGraph[m,n]
gives the n-dimensional De Bruijn graph with m symbols.

DeBruijnGraph[m,n,type]
gives the De Bruijn graph with connectivity given by type.

Details and OptionsDetails and Options

  • DeBruijnGraph[m,n] has vertices, consisting of all length-n sequences of m symbols. Given two vertices and , there is an edge from v to , provided , , , .
  • DeBruijnGraph[m,n,type] specifies different connectivity types. The following types can be given:
  • "Noncyclic", ,
    "LeftShift", , ,
    "RightShift", , ,
  • DeBruijnGraph[] is a directed graph.
  • DeBruijnGraph takes the same options as Graph.

ExamplesExamplesopen allclose all

Basic Examples  (3)Basic Examples  (3)

The first few De Bruijn graphs with two symbols and different dimensions:

In[1]:=
Click for copyable input
Out[1]=

De Bruijn graphs with different numbers of symbols in dimension two:

In[1]:=
Click for copyable input
Out[1]=

De Bruijn graphs with different connectivity types:

In[1]:=
Click for copyable input
Out[1]=
Introduced in 2010
(8.0)