MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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