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!
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
4
|
||||||||||||||
|
|
9
|
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}$). |
||
|
|
