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 mn vertices, consisting of all length-n sequences of m symbols. Given two vertices v={s1,,sn} and ={t1,,tn}, there is an edge from v to , provided s2==t1, s3==t2, , sn==tn-1.
  • DeBruijnGraph[m,n,type] specifies different connectivity types. The following types can be given:
  • "Noncyclic"s_(2)⩵t_(1), , s_(n)⩵t_(n-1)
    "LeftShift"s_(1)⩵t_(n), s2t1, , sn t_(n-1)
    "RightShift"s_(2)⩵t_(2), , s_(n-1)⩵t_(n), s_(n)⩵t_(1)
  • 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)
Translate this page: