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

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|improve this question
This is it: en.wikipedia.org/wiki/Hamming_graph –  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
add comment

1 Answer 1

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|improve this answer
add comment

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.