- Tytuł:
- Colouring of cycles in the de Bruijn graphs
- Autorzy:
-
Łazuka, Ewa
Żurawiecki, Jerzy - Powiązania:
- https://bibliotekanauki.pl/articles/743669.pdf
- Data publikacji:
- 2000
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
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 - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 5-21
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł