Abstract

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.

Key words: Graph homomorphism, Lempel homomorphism, de Bruijn sequence, de Bruijn graphs.