What is the name of this graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T14:57:53Z http://mathoverflow.net/feeds/question/65546 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65546/what-is-the-name-of-this-graph What is the name of this graph? Hilary Finucane 2011-05-20T14:43:19Z 2011-05-20T15:03:08Z <p>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!</p> http://mathoverflow.net/questions/65546/what-is-the-name-of-this-graph/65549#65549 Answer by Johan Wästlund for What is the name of this graph? Johan Wästlund 2011-05-20T15:03:08Z 2011-05-20T15:03:08Z <p>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}\$).</p>