MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I think this graph has a name: the vertices are bit strings of length $n$, and $(x_1, \ldots , x_n)$ is connected to $(x_2, \ldots, x_n, 0)$, $(x_2, \ldots, x_n, 1)$, $(0,x_1, \ldots , x_{n-1})$ and $(1, x_1, \ldots , x_{n-1})$. I'm wondering (a) what the name is and (b) where I can read more about this graph. Thanks!

share|cite|improve this question
This is it: – Per Alexandersson May 20 '11 at 14:52
Isn't Hamming graphs where vertices are connected when they differ in one entry? Here the operation is shifting one step. – Johan Wästlund May 20 '11 at 15:05
I think Concrete Mathematics mentions this graph, but I'm not sure, and I can't check it right now because I'm not at home. – Zsbán Ambrus May 30 '11 at 8:50
up vote 9 down vote accepted

They are called De Bruijn graphs (De Bruijn graphs are generally considered directed, and can be defined over any set of symbols, not just $\{0,1\}$).

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.