Geodesic
Colouring of cycles in the de Bruijn graphs
Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 5-21

Voir la notice de l'article provenant de la source Library of Science

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.
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 
@article{DMGT_2000_20_1_a0,
     author = {{\L}azuka, Ewa and \.Zurawiecki, Jerzy},
     title = {Colouring of cycles in the de {Bruijn} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--21},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2000},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a0/}
}
TY  - JOUR
AU  - Łazuka, Ewa
AU  - Żurawiecki, Jerzy
TI  - Colouring of cycles in the de Bruijn graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2000
SP  - 5
EP  - 21
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a0/
LA  - en
ID  - DMGT_2000_20_1_a0
ER  - 
%0 Journal Article
%A Łazuka, Ewa
%A Żurawiecki, Jerzy
%T Colouring of cycles in the de Bruijn graphs
%J Discussiones Mathematicae. Graph Theory
%D 2000
%P 5-21
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a0/
%G en
%F DMGT_2000_20_1_a0
Łazuka, Ewa; Żurawiecki, Jerzy. Colouring of cycles in the de Bruijn graphs. Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 5-21. http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a0/