 DeBruijnGraph - Maple Help

GraphTheory[SpecialGraphs]

 DeBruijnGraph
 construct De Bruijn graph Calling Sequence DeBruijnGraph(m,n) DeBruijnGraph(s,n) Parameters

 m - positive integer n - positive integer s - string of distinct characters Description

 • 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. Examples

 > $\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\left(s\right), and 3 self-loop\left(s\right)}}$ (1)
 > $\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\left(s\right), and 5 self-loop\left(s\right)}}$ (2)
 > $\mathrm{NumberOfSelfLoops}\left(\mathrm{G53}\right)$
 ${5}$ (3)
 > $\mathrm{NumberOfEdges}\left(\mathrm{G53}\right)$
 ${625}$ (4)
 > $\mathrm{IsEulerian}\left(\mathrm{G53}\right)$
 ${\mathrm{true}}$ (5) Compatibility

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