UNIFORM HOMOMORPHISMS OF DE-BRUIJN AND KAUTZ NETWORKS

In this paper, we study the problem of homomorphisms of a general clas s of line digraphs. We show that the homomorphisms can always be defin ed 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 u niform 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 homo morphisms and shortest-path spanning trees of B/K digraphs, we also de scribe optimal emulations of Divide&Conquer computations on B/K digrap hs. (C) 1998 Elsevier Science B.V. All rights reserved.