Characterization of de Bruijn graphs homomorphisms

African Journal of Mathematics and Computer Science Research

Akinw¹ 

关键词: Graph homomorphism;    Lempel homomorphism;    de Bruijn sequence;    de Bruijn graphs.;   

DOI  :  

学科分类：计算机科学（综合）

来源: Academic Journals

【 摘 要 】

We study homomorphisms between de Bruijn digraphs of different orders. A main theme of this paper is to characterize de Bruijn graph homomorphisms such that the inverse of a factor in the lower order digraph is also a factor in the higher order one, where a factor is a collection of cycles that partition the digraph. We generalize Lempel's homomorphism by describing and characterizing a class of homomorphisms between two de Bruijn digraphs of arbitrarily different orders but with the same alphabet, the direction of these functions being of course from the higher order digraph to the lower order one. Finally, we single out the binary case, which due to its simplicity admits a more concise characterization.

【 授权许可】

CC BY