Arc fault tolerance of cartesian product digraphs on hyper arc connectivity

摘要

A strongly connected digraph D is hyper-λ if the removal of any minimum arc cut of D results in exactly two strong components, one of which is a singleton. We define a hyper-λ digraph D to be m-hyper-λ if D - S is still hyper-λ for any arc set S with |S| ≤ m. The maximum integer of such m, denoted by H_λ (D), is said to be the arc fault tolerance of D on the hyper-λ property. H_λ (D) is an index to measure the reliability of networks. In this paper, we study H_λ(D) for the cartesian product digraph D + D_1 × D_2. We give a necessary and sufficient condition for D_1×D_2 to be hyper-λ and give the lower and upper bounds on H_λ(D_1× D_2). An example shows that the lower and upper bounds are best possible. In particular, exact values of H_λ(D_1 × D_2) are obtained in special cases. These results are also generalized to the cartesian product of n strongly connected digraphs.