De Bruijn graph


Also found in: Wikipedia.

De Bruijn graph

(mathematics)
A class of graphs with elegant properties.

De Bruijn graphs are especially easy to use for routing, with shifting of source and destination addresses.

References in periodicals archive ?
One of the classical objects in combinatorics is the De Bruijn graph.
The De Bruijn graph has been much studied, especially in connection with combinatorics on words, and one of its well known properties is the fact that its number of directed cycles of length d, for d [less than or equal to] n, is given by
A natural variation on the De Bruijn graphs is obtained by replacing words over an alphabet by permutations of the set of integers {1, 2, .
Keywords: Analytic methods, asymptotics, autocorrelation, average-case analysis, combinatorias on words, correlation polynomial, de Bruijn graph, depth, subword complexity, suffix trees.
Then the adjacency matrix of the de Bruijn graph [B.
where I is the identity matrix and Mn is the adjacency matrix of the de Bruijn graph Bn(A).
In this section we show the connection between different types of correlation polynomial matrices, the adjacency matrix of the de Bruijn graph and subword complexity related generating functions.
k] (z) in terms of the adjacency matrix of the de Bruijn graph.
Let Mn denote the adjacency matrix of the de Bruijn graph [B.
Considering the relative simplicity of the adjacency matrix of the de Bruijn graph, we give a method of computing all the generalized correlation polynomials of words of length n.