Cayley Digraphs Based on the de Bruijn Networks
María José Espona, Oriol Serra · SIAM Journal on Discrete Mathematics · 1998
A construction of Cayley digraphs associated to arc-colored regular digraphs is presented. The resulting Cayley digraphs, which we call Cayley regular covers, can be seen as a symmetrization of the original digraph. This construction is applied to the de Bruijn digraphs. By using the fact that they are iterated line digraphs of complete symmetric digraphs, valuable information about their Cayley regular covers regarding routings, diameter, hamiltonicity, fault-tolerance properties and degree of symmetry is obtained. In particular, a shortest-path, self-routing algorithm is given for a family of Cayley digraphs which includes the well known butterfly network. These results can be applied to the design of permutation networks. The Cayley regular covers represent sets of permutations in the original digraph which can be performed without conflict. In particular, a sharply 2-transitive group of permutations on the de Bruijn network is presented which admits a simple shortest-path self-routing algorithm. By using the same construction, a Cayley digraph on the symmetric group on the nodes of the de Bruijn digraph of degree two is obtained. The techniques introduced in this paper can also be extended to other families of iterated line digraphs.