Arc fault tolerance of cartesian product digraphs on hyper arc connectivity

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=D₁×D₂. We give a necessary and sufficient condition for D₁×D₂ to be hyper-λ and give the lower and upper bounds on H_λ(D₁×D₂). An example shows that the lower and upper bounds are best possible. In particular, exact values of H_λ(D₁×D₂) are obtained in special cases. These results are also generalized to the cartesian product of n strongly connected digraphs.

Keywords:

• arc fault tolerance
• hyper arc connectivity
• cartesian product digraph
• interconnection network

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).