# Hamiltonian circuit for a family of graphs

For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$.

Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For instance, $bbaaaababaabbbba \in C_4$

I have formulated the problem of finding the subset of $C_n$, formed by the circular strings with the smallest size ($=2^n$), as the problem of finding all hamiltonian circuits on the graph that has the elements of $S_n$ as vertices, and edges connecting all pairs of vertices $s_i$ and $s_j$ such that $s_i = xw$ and $s_j = wy$, with $w \in \Sigma^{n-1}$ and $x,y \in \Sigma$.

For the example above, the graph could look like this:

My question:

Would there be a polynomial-time solution for the hamilton circuit problem restricted to this family of graphs?

• It feels like this might be related to $n$-ary Grey codes, which are a way of enumerating the length-$k$ strings from an $n$-symbol alphabet such that adjacent elements of the enumeration differ by exactly one character. That's not quite what you want but it's similar. (Yuval's answer appeared while I was writing this comment; I'm posting the comment anyway in case it turns out to be useful.) – David Richerby May 16 '15 at 14:45