Tell me more ×  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: –  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  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