Arc fault tolerance of cartesian product digraphs on hyper arc connectivity
Guozhen Zhang · International Journal of Computer Mathematics · 2014
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.