Length of shortest word that contains all triples

Question

Given a finite set $M := \{1...n\}$, what is the shortest word $w \in M^*$ so that the set of all subwords of $w$ is a superset of $M^3$? A subword is a prefix of a suffix.

For $1 \leq n \leq 2$ it is $n^3+2$ and I assume this holds for every $n$.

Answer 1

As stated in the comments by Arthur, the De Brujin graph of all words in $M^3$ is hamiltonian. Pick a node (i.e. a word of length 3) and walk an Hamilton path of length $n^3-1$. Since every edge adds a single character to the previous word, this yields a word of length $3 + n^3 - 1$ that contains every word of length 3.