5
$\begingroup$

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:

enter image description here

My question:

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – David Richerby
    Commented May 16, 2015 at 14:45

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ In particular, every de Bruijn graph is Hamiltonian. $\endgroup$
    – David Richerby
    Commented May 16, 2015 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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