Abstract
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=D1×D2. We give a necessary and sufficient condition for D1×D2 to be hyper-λ and give the lower and upper bounds on Hλ(D1×D2). An example shows that the lower and upper bounds are best possible. In particular, exact values of Hλ(D1×D2) are obtained in special cases. These results are also generalized to the cartesian product of n strongly connected digraphs.
Acknowledgements
The author thanks Prof. Shiying Wang for his valuable suggestions. The author also thanks the anonymous referees for the constructive suggestions and comments that improve the quality of this paper. This work is supported by the National Natural Science Foundation of China (61070229, 61202017) and the Doctoral Fund of Ministry of Education of China (20111401110005).