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 studies 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 trails in Eulerizations of unoriented de Bruijn graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
de Bruijn, N.G.: A combinatorial problem. Nederl. Akad. Wetensch. Proc. 49, 758–764 (1946)
de Bruijn N. G.: Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of \(2^n\) zeros and ones that show each n-letter word exactly once, Technological University Eindhoven Report 75-WSK-06 1-14 (1975)
Edmonds, J., Johnson, E.L.: Matching Euler tours and the Chinese postman problem. Math. Program. 5, 88–124 (1973)
Esfahanian, A.-H., Hakimi, S.L.: Fault-tolerant routing in de Bruijn communication networks. IEEE Trans. Comput. 34(9), 777–788 (1985)
Fleury, M.: Deux problmes de Géométrie de situation. J. de mathématiques élémentaires 2nd Ser 2, 257–261 (1883)
Hierholzer, C.: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6(1), 30–32 (1873)
Kuo, J., Fu, H.-L.: On the diameter of the generalized undirected de Bruijn graphs UGB(n, m), \(n^{2} < m \le n^3\). Networks 52(4), 180–182 (2008)
Kari, L., Xu, Z.: de Bruijn sequences revisited. In: Dömösi, P., Iván, Sz. (eds.) Automata and Formal Languages, Proceedings 2011, pp. 241–254 (2016)
Lu, C., Xu, J., Zhang, K.: On \((d,2)\)-dominating numbers of binary undirected de Bruijn graphs. Discret. Appl. Math. 105(13), 137–145 (2000)
Motta, F.C., Shipman, P.D., Springer, B.: A point of tangency between combinatorics and differential geometry. Am. Math. Mon. 122, 52–55 (2015)
Motta, F.C., Shipman, P.D., Springer, B.: Optimally topologically transitive orbits in discrete-time dynamical systems. Am. Math. Mon. 123(2), 115–135 (2016)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Burris, C.S., Motta, F.C. & Shipman, P.D. An Unoriented Variation on de Bruijn Sequences. Graphs and Combinatorics 33, 845–858 (2017). https://doi.org/10.1007/s00373-017-1793-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1793-4