We show that the problem of finding the family of all so called the locally reducible factors in the binary de Bruijn graph of order k is equivalent to the problem of finding all colourings of edges in the binary de Bruijn graph of order k-1, where each vertex belongs to exactly two cycles of different colours. In this paper we define and study such colouring for the greater class of the de Bruijn graphs in order to define a class of so called regular factors, which is not so difficult to construct. Next we prove that each locally reducible factor of the binary de Bruijn graph is a subgraph of a certain regular factor in the m-ary de Bruijn graph.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1103,
author = {Ewa \L azuka and Jerzy \.Zurawiecki},
title = {Colouring of cycles in the de Bruijn graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {20},
year = {2000},
pages = {5-21},
zbl = {0963.05054},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1103}
}
Ewa Łazuka; Jerzy Żurawiecki. Colouring of cycles in the de Bruijn graphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 5-21. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1103/
[000] [1] M. Cohn and A. Lempel, Cycle decomposition by disjoint transpositions, J. Combin. Theory (A) 13 (1972) 83-89, doi: 10.1016/0097-3165(72)90010-6. | Zbl 0314.05005
[001] [2] E.D. Erdmann, Complexity measures for testing binary keystreams, PhD thesis, Stanford University, 1993.
[002] [3] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Rev. 24 (1982) 195-221, doi: 10.1137/1024041. | Zbl 0482.68033
[003] [4] E.R. Hauge and T. Helleseth, De Bruijn sequences, irreducible codes and cyclotomy, Discrete Math. 159 (1996) 143-154, doi: 10.1016/0012-365X(96)00106-9. | Zbl 0878.94046
[004] [5] C.J.A. Jansen, Investigations on nonlinear strimcipher systems: Construction and evaluation methods, PhD thesis, Technical University of Delft, 1989.
[005] [6] M. Łatko, Design of the maximal factors in de Bruijn graphs, (in Polish), PhD thesis, UMCS, 1987.
[006] [7] E. Łazuka and J. Żurawiecki, The lower bounds of a feedback function, Demonstratio Math. 29 (1996) 191-203. | Zbl 0865.94019
[007] [8] R.A. Rueppel, Analysis and design of stream ciphers (Springer-Verlag, 1986).
[008] [9] P. Wlaź and J. Żurawiecki, An algorithm for generating M-sequences using universal circuit matrix, Ars Combinatoria 41 (1995) 203-216. | Zbl 0854.05075
[009] [10] J. Żurawiecki, Elementary k-iterative systems (the binary case), J. Inf. Process. Cybern. EIK 24 1/2 (1988) 51-64. | Zbl 0654.94013
[010] [11] J. Żurawiecki, Locally reducible iterative systems, Demonstratio Math. 23 (1990) 961-983. | Zbl 0747.94009