An Unoriented Variation on de Bruijn Sequences

2016/08/30 by Burris, Christie S., Motta, Francis C., Shipman, Patrick D.
#05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.08480

Abstract

For positive integers k,n, a de Bruijn sequence B(k,n) is a finite sequence of elements drawn from k characters whose subwords of length n are exactly the kⁿ words of length n on k characters. This paper introduces the unoriented de Bruijn sequence uB(k,n), an analog to de Bruijn sequences, but for which the sequence is read both forwards and backwards to determine the set of subwords of length n. We show that nontrivial unoriented de Bruijn sequences of optimal length exist if and only if k is two or odd and n is less than or equal to 3. Unoriented de Bruijn sequences for any k, n may be constructed from certain Eulerian paths in Eulerizations of unoriented de Bruijn graphs.

Related

• Cut-Down de Bruijn Sequences
• Extending de Bruijn sequences to larger alphabets
• Minimum de Bruijn Sequence in a Language with Forbidden Substrings
• Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences
• Contributions to the theory of de Bruijn cycles