## Construction of small superpermutations and minimal injective superstrings.(English)Zbl 0801.05004

Summary: A superpermutation is a string over an alphabet $$\mathcal A$$ that contains every permutation of the elements of $$\mathcal A$$ as a contiguous substring. In this paper, we present a recursive construction for a very small superpermutation on the alphabet $${\mathcal A}= \{1,2,\dots,n\}$$. We also treat the case where every string of length $$k< n$$ with no repeated characters is to appear as a contiguous substring. Such a string is called an injective superstring on strings of length $$k$$ over $$\mathcal A$$.

### MSC:

 05A05 Permutations, words, matrices 05C99 Graph theory 68R15 Combinatorics on words 05C20 Directed graphs (digraphs), tournaments

### Keywords:

superpermutation; string; injective superstring