FAULT-TOLERANT FIXED ROUTINGS IN SOME FAMILIES OF DIGRAPHS

The purpose of this paper is to find fault-tolerant fixed routings in some families of digraphs that have been widely considered into the de sign of interconnection networks. A routing rho in a digraph G assigns to each pair of vertices a fixed path (called a route) between them. For a given set of faulty vertices and/or arcs, the vertices of the su rviving route digraph are the nonfaulty vertices and there is an arc b etween two vertices if and only if there are no faults on the route be tween them. The diameter of the surviving route digraph measures the f ault tolerance of the routing. In this work, sufficient conditions are found for a digraph to have a routing such that for any set of faults with a bounded number of elements the diameter of the surviving route digraph is at most 3. These results are applied to prove the existenc e of routings with this property in the generalized de Bruijn and Kaut z digraphs, the bipartite digraphs BD(d, n), and general iterated line digraphs.