PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
de Bruijn digraph (Definition)

The vertices of the de Bruijn digraph $ B(n,m)$ are all possible words of length $ m-1$ chosen from an alphabet of size $ n$.

$ B(n,m)$ has $ n^{m}$ edges consisting of each possible word of length $ m$ from an alphabet of size $ n$. The edge $ a_1a_2\dots a_n$ connects the vertex $ a_1a_2\dots a_{n-1}$ to the vertex $ a_2a_3\dots a_n$.

For example, $ B(2,4)$ could be drawn as:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & 000 \ar@(ur,ul)[]_{0000} \ar[d... ...110} \ar[dl]^{0111}\ & 111 \ar@(dl,dr)[]_{1111} \ar[ul]^{1110} & } } \end{xy}$

Notice that an Euler cycle on $ B(n,m)$ represents a shortest sequence of characters from an alphabet of size $ n$ that includes every possible subsequence of $ m$ characters. For example, the sequence $ 000011110010101000$ includes all 4-bit subsequences. Any de Bruijn digraph must have an Euler cycle, since each vertex has in degree and out degree of $ n$.



"de Bruijn digraph" is owned by Mathprof. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: Kautz graph, line graph

Log in to rate this entry.
(view current ratings)

Cross-references: in degree, subsequence, characters, sequence, represents, Euler cycle, vertex, edges, size, alphabet, length, vertices
There is 1 reference to this entry.

This is version 4 of de Bruijn digraph, born on 2002-02-02, modified 2006-11-13.
Object id is 1699, canonical name is DeBruijnDigraph.
Accessed 4096 times total.

Classification:
AMS MSC05C20 (Combinatorics :: Graph theory :: Directed graphs , tournaments)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)