Arc Fault Tolerance of Maximally Arc-Connected Networks Modeled By Digraphs

The underlying topology of an interconnection network can be modeled by a digraph D = (V, A). A strongly connected digraph D is maximally arc-connected if its arc-connectivity is equal to its minimum degree. The maximally arc-connected tolerance m(lambda) (D) to arc-faults of a maximally arc-connected digraph D is the maximum integer f, for which D - S is still maximally arc-connected for any set S subset of A(D) with vertical bar S vertical bar <= f. The index m(lambda) (D) is used to measure the reliability of networks. In this paper, we present upper and lower bounds on m(lambda) (D). More refined bounds are obtained under some conditions, from which the exact values of m(lambda) (D) are determined for some networks modeled by digraphs.