The -de
Bruijn graph is a non-simpleregulardirected graph whose nodes are sequences of copies of symbols from some alphabet and
whose edges consist of pairs of vertices such that shifting the symbols of the first
vertex by one place to the left and adding any symbol at the end corresponds to the
symbol of the second vertex. For example, the -de Bruijn graph is illustrated above.
The above figures show the first few -dimensional de Bruijn graphs on copies of symbols for .
The independence number of the de Bruijn graphs for , 2, ... are given by 1, 2, 3, 7, 13, 28, ... (OEIS A006946).
The -Kautz graph can be obtained from the -de Bruijn graph by removing vertices whose symbols contain
two or more identical letters (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.; and Medvedev, P. "On the Representation of De
Bruijn Graphs." J. Comput. Biol.22, 336-352, 2014.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éiaire 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 is a non-simple regular directed graph whose nodes are sequences of 
copies of 
symbols from some alphabet and
whose edges consist of pairs of vertices such that shifting the symbols of the first
vertex by one place to the left and adding any symbol at the end corresponds to the
symbol of the second vertex. For example, the 
-de Bruijn graph is illustrated above.
-dimensional de Bruijn graphs on 
copies of 
symbols for 
.
-de
Bruijn graph is implemented in the Wolfram
Language as DeBruijnGraph[m,
n].
-de
Bruijn graph with self-loops removed.
-de
Bruijn graph has vertex count 
, edge count 
, 
self-loops, graph diameter 
, and maximum
vertex degree 
.
for 
, 2, ... are given by 1, 2, 3, 7, 13, 28, ... (OEIS A006946).
-Kautz graph can be obtained from the 
-de Bruijn graph by removing vertices whose symbols contain
two or more identical letters (Bermond et al. 1986).
