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!
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

