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

Ashlock, Daniel A.; Tillotson, Jenett

Congr. Numerantium 93, 91-98 (1993).

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