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!

  • 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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.