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_{n1})$ and $(1, x_1, \ldots , x_{n1})$. I'm wondering (a) what the name is and (b) where I can read more about this graph. Thanks!
5

1$\begingroup$ This is it: en.wikipedia.org/wiki/Hamming_graph $\endgroup$ – Per Alexandersson May 20 '11 at 14:52

6$\begingroup$ Isn't Hamming graphs where vertices are connected when they differ in one entry? Here the operation is shifting one step. $\endgroup$ – Johan Wästlund May 20 '11 at 15:05

$\begingroup$ 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. $\endgroup$ – Zsbán Ambrus May 30 '11 at 8:50
9
$\begingroup$
$\endgroup$
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\}$).