Given an alphabel $\Sigma$, a sequence $\bar{s}$ in $\Sigma^*$ is said to be k-universal if it contains all sub-sequences of $\Sigma^k$. I am interested by the smallest of these k-universal sequences. Of course, it should have length at least $|\Sigma|^k + k - 1$. Empirically, there are a lot of k-universal sequences of this length.
For example, for $\Sigma = \{0, 1\}$ and $k = 3$, a few of these sequences are 0001011100, 0001110100 and 0010111000. Each of them has a length of $10 = 2^3 + 3 - 1$ and contains all the sub-sequences 000, 001, 010, 011, 100, 101, 110 and 111.
Is there a fast way to find smallest k-universal sequences, even just one?
What I've tried
Looking for such sequences with a binary alphabet $\Sigma = \{0, 1\}$, I found out that we could model this problem as finding an Hamiltonian path (going through all vertices) on an oriented graph G(V, E), where the vertices V are the sequences of $\Sigma^k$ and for each $x,y \in \Sigma, \bar{s} \in \Sigma^{k-1}$, there is an edge $(x\bar{s}) \to (\bar{s}y) \in$ E. For $k = 1, 2, 3, 4$, I rendered manually the graphs below:
However, computing an Hamiltonian path is an NP-complete problem in general, and after implementing it this solution does not scale. Is there a more generative way to obtain the smallest k-universal numbers, e.g. with grammars?