Arc Fault Tolerance of Maximally Arc-Connected Networks Modeled By Digraphs. (9th August 2018) - Zhao, Shuang; Meng, Jixiang
Abstract: 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 λ ( 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 ⊆ A ( D ) with | S | ≤ f . The index m λ ( D ) is used to measure the reliability of networks. In this paper, we present upper and lower bounds on m λ ( D ) . More refined bounds are obtained under some conditions, from which the exact values of m λ ( D ) are determined for some networks modeled by digraphs.