An unoriented variation on de Bruijn sequences

DOI10.1007/S00373-017-1793-4MaRDI QIDQ2409522zbMATHOpenAlexFDO

Authors Christie S. Burris, Francis Motta, Patrick D. Shipman

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08480

zbMATH Keywords

de Bruijn sequencede Bruijn graphEulerian trail

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Eulerian and Hamiltonian graphs (05C45) Special sequences and polynomials (11B83)

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^n$ 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.

Recommendations

• de Bruijn sequences and de Bruijn graphs for a general language
• On Leaf Node Edge Switchings in Spanning Trees of De Bruijn Graphs
• De Bruijn sequences revisited
• scientific article; zbMATH DE number 2192127
• De Bruijn sequences with varying combs

Cites work

• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A point of tangency between combinatorics and differential geometry
• De Bruijn sequences revisited
• Fault-Tolerant Routing in DeBruijn Comrnunication Networks
• Matching, Euler tours and the Chinese postman
• On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
• On the diameter of the generalized undirected de Bruijn graphsUG_B(n,m),n²<m≤n³
• Optimally Topologically Transitive Orbits in Discrete Dynamical Systems

Cited in

(4)

• scientific article; zbMATH DE number 721897 (Why is no real title available?)
• Graph-Theoretic Concepts in Computer Science
• Constructing orthogonal de Bruijn sequences
• A note on certain de Bruijn sequences with forbidden subsequences

This page was built for publication: An unoriented variation on de Bruijn sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409522)