DeBruijnGraph(m,n) returns the De Bruijn graph, a directed graph whose vertices may be seen as sequences of symbols of length n chosen from some alphabet of size m and whose edges indicate those sequences which may overlap.

The graph has $m^n$ vertices, each of which corresponds to a sequence of the $m$ symbols of length $n$.

DeBruijnGraph(s,n) returns a De Bruijn graph equivalent to DeBruijnGraph(length(s),n) but whose vertices are strings of length n composed from the characters in s. There is a directed edge from string t1 to a string t2 if there exists a string v of length n-1 and characters u,w in s such that t1=cat(u,v) and t2=cat(v,w).

The graph is named for Nicolaas Govert de Bruijn.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$\mathrm{G32}≔\mathrm{DeBruijnGraph}\left(3\,2\right)$

$\mathrm{G32}≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 9\; vertices,\; 24\; arc(s),\; and\; 3\; self-loop(s)}$

$\mathrm{DrawGraph}\left(\mathrm{G32}\right)$

$\mathrm{G53}≔\mathrm{DeBruijnGraph}\left(5\,3\right)$

$\mathrm{G53}≔\mathrm{Graph\; 2:\; a\; directed\; graph\; with\; 125\; vertices,\; 620\; arc(s),\; and\; 5\; self-loop(s)}$

$\mathrm{NumberOfSelfLoops}\left(\mathrm{G53}\right)$

$5$

$\mathrm{NumberOfEdges}\left(\mathrm{G53}\right)$

$625$

$\mathrm{IsEulerian}\left(\mathrm{G53}\right)$

$\mathrm{true}$

The GraphTheory[SpecialGraphs][DeBruijnGraph] command was introduced in Maple 2020.

For more information on Maple 2020 changes, see Updates in Maple 2020.

The GraphTheory[SpecialGraphs][DeBruijnGraph] command was updated in Maple 2023.

The s parameter was introduced in Maple 2023.

For more information on Maple 2023 changes, see Updates in Maple 2023.