This graph is known as a [de Bruijn graph][1], and its Hamiltonian circuits are known as [de Bruijn sequences][2]. Both are well understood (for example, we know exactly how many of these exist).


  [1]: http://en.wikipedia.org/wiki/De_Bruijn_graph
  [2]: http://en.wikipedia.org/wiki/De_Bruijn_sequence