# What is the name of this graph?

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!

-
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

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\}$).

-