Uniform homomorphisms of de Bruijn and Kautz networks

In this paper, we study the problem of homomorphisms of a general class of line digraphs. We show that the homomorphisms can always be defined using a partial binary operation on the alphabet whose letters form labels of the vertices. We apply these results to de Bruijn and Kautz (in short B/K) digraphs to characterize their uniform homomorphisms. For d non-prime, we describe algorithms for constructing non-trivial uniform homomorphisms of d-ary B/K digraphs of diameter D onto d-ary B/K digraphs of diameter D - 1. Using the properties of the uniform homomorphisms and shortest-path spanning trees of B/K digraphs, we also describe optimal emulations of Divide&Conquer computations on B/K digraphs. (C) 1998 Elsevier Science B.V. All rights reserved.