Colouring of cycles in the de Bruijn graphs

Ewa Łazuka; Jerzy Żurawiecki

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 1, page 5-21
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ewa Łazuka, and Jerzy Żurawiecki. "Colouring of cycles in the de Bruijn graphs." Discussiones Mathematicae Graph Theory 20.1 (2000): 5-21. <http://eudml.org/doc/270512>.

@article{EwaŁazuka2000,
abstract = {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.},
author = {Ewa Łazuka, Jerzy Żurawiecki},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {the de Bruijn graph; decomposition; colouring of edges in a cycle; factors of the de Bruijn graph; locally reducible factor; feedback function; locally reducible function; de Bruijn graph; cycles; colourings},
language = {eng},
number = {1},
pages = {5-21},
title = {Colouring of cycles in the de Bruijn graphs},
url = {http://eudml.org/doc/270512},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Ewa Łazuka
AU - Jerzy Żurawiecki
TI - Colouring of cycles in the de Bruijn graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 5
EP - 21
AB - 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.
LA - eng
KW - the de Bruijn graph; decomposition; colouring of edges in a cycle; factors of the de Bruijn graph; locally reducible factor; feedback function; locally reducible function; de Bruijn graph; cycles; colourings
UR - http://eudml.org/doc/270512
ER -

References

top
  1. [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. Zbl0314.05005
  2. [2] E.D. Erdmann, Complexity measures for testing binary keystreams, PhD thesis, Stanford University, 1993. 
  3. [3] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Rev. 24 (1982) 195-221, doi: 10.1137/1024041. Zbl0482.68033
  4. [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. Zbl0878.94046
  5. [5] C.J.A. Jansen, Investigations on nonlinear strimcipher systems: Construction and evaluation methods, PhD thesis, Technical University of Delft, 1989. 
  6. [6] M. Łatko, Design of the maximal factors in de Bruijn graphs, (in Polish), PhD thesis, UMCS, 1987. 
  7. [7] E. Łazuka and J. Żurawiecki, The lower bounds of a feedback function, Demonstratio Math. 29 (1996) 191-203. Zbl0865.94019
  8. [8] R.A. Rueppel, Analysis and design of stream ciphers (Springer-Verlag, 1986). 
  9. [9] P. Wlaź and J. Żurawiecki, An algorithm for generating M-sequences using universal circuit matrix, Ars Combinatoria 41 (1995) 203-216. Zbl0854.05075
  10. [10] J. Żurawiecki, Elementary k-iterative systems (the binary case), J. Inf. Process. Cybern. EIK 24 1/2 (1988) 51-64. Zbl0654.94013
  11. [11] J. Żurawiecki, Locally reducible iterative systems, Demonstratio Math. 23 (1990) 961-983. Zbl0747.94009

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.