3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Meyerowitz
    Commented May 25, 2012 at 23:30
  • $\begingroup$ 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? $\endgroup$
    – Aaron Meyerowitz
    Commented May 26, 2012 at 2:29

0

Reset to default

You must log in to answer this question.