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

