An unoriented variation on de Bruijn sequences

DOI10.1007/S00373-017-1793-4zbMATH Open1371.05004arXiv1608.08480OpenAlexW2963629058MaRDI QIDQ2409522FDOQ2409522

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

Publication date: 11 October 2017

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matching, Euler tours and the Chinese postman
• Fault-Tolerant Routing in DeBruijn Comrnunication Networks
• On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs
• Optimally Topologically Transitive Orbits in Discrete Dynamical Systems
• A Point of Tangency Between Combinatorics and Differential Geometry
• On the diameter of the generalized undirected de Bruijn graphsUG_B(n,m),n²<m≤n³

Cited In (1)

• Title not available (Why is that?)

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)