The -de
Bruijn graph, for integers and , is the directed graph
whose vertices are the words of length over an alphabet of symbols. There is a directed
edge from one word to another when deleting the first symbol and appending one
symbol gives the second word. The graph has self-loops.
For example, the -de
Bruijn graph is illustrated above.
The above figures show the first few -dimensional de Bruijn graphs on an alphabet
of symbols for .
For ,
the -Kautz graph is obtained from the -de Bruijn graph by removing the vertices
whose words contain two consecutive identical symbols (Bermond et al. 1986).
Bermond, J.-C.; Delorme, C.; and Quisquater, J.-J. "Strategies for Interconnection Networks: Some Methods from Graph Theory." J. Parallel
and Distributed Comput.3, 433-449, 1986.Chikhi, R.; Limasset,
A.; Jackman, S.; Simpson, J. T.; and Medvedev, P. "On the Representation
of De Bruijn Graphs." J. Comput. Biol.22, 336-352, 2015.de
Bruijn, N. G. "A Combinatorial Problem." Koninkl. Nederl. Acad.
Wetensch. Proc. Ser. A49, 758-764, 1946.Flye Sainte-Marie,
C. "Question 48." L'Intermédiaire des Math.1, 107-110,
1894.Golomb, S. W. Shift
Register Sequences. San Francisco, CA: Holden-Day, 1967.Good,
I. J. "Normal Recurring Decimals." J. London Math. Soc.21,
167-169, 1946.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."Zhang,
F. J. and Lin, G. N. "On the De Bruijn-Good Graphs." Acta
Math. Sinica30, 195-205, 1987.
-de
Bruijn graph, for integers 
and 
, is the directed graph
whose vertices are the words of length 
over an alphabet of 
symbols. There is a directed
edge from one word to another when deleting the first symbol and appending one
symbol gives the second word. The graph has self-loops.
For example, the 
-de
Bruijn graph is illustrated above.
-dimensional de Bruijn graphs on an alphabet
of 
symbols for 
.
-de
Bruijn graph is implemented in the Wolfram
Language as DeBruijnGraph[m,
n].
-de
Bruijn graph, obtained by forgetting edge directions and removing self-loops.
-de
Bruijn graph has vertex count 
, edge count 
, 
self-loops, directed graph
diameter 
,
and indegree and outdegree 
at every graph
vertex.
-de Bruijn graphs for 
, 2, ... are 1, 2, 3, 7, 13, 28, ... (OEIS A006946).
,
the 
-Kautz graph is obtained from the 
-de Bruijn graph by removing the vertices
whose words contain two consecutive identical symbols (Bermond et al. 1986).
