Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have encountered sets of the following type, consisting of words over a finite aphabet $A$.

If $S$ is such a set, then

  1. $S$ is finite,

  2. No word in $S$ is part of another element of $S$, and

  3. every infinite sequence $\dots a_{-2} a_{-1} a_0 a_1 a_2 \dots$ of elements of $A$ can be covered by elements of $S$ in the following sense: for every $k \in \mathbb Z$ there are numbers $i$, $j$ with $i \leq k \leq j$ such that $a_i a_{i + 1} \dots a_j \in S$.

Now I take the elements of $S$ as vertices of a directed graph $G$ with loops; an edge between two words $w_1$, $w_2 \in S$ exists exactly then when there is a sequence of elements of $A$ in which $w_1$ is followed directly by $w_2$.

If $S = A^n$, the set of all words of length $n$, then $G$ is a de Bruijn graph. But what about the general case? Has anyone written about it, or do you know anything interesting about such graphs?

share|improve this question
Can you give an example or two of such a set S aside from all words of length $n$? If we restrict to the words of S with only 2 of the given letters that has the same properties so an example like that would be enough. –  Aaron Meyerowitz May 25 '12 at 23:30
Also, what is the question? A DeBruijn graph is a certain kind of graph. The big result is that it has a Hamilton cycle (or Euler cycle depending on the view) are you asking if that applies in your situation? –  Aaron Meyerowitz May 26 '12 at 2:29
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.