Arc fault tolerance of cartesian product digraphs on hyper arc connectivity

作者：Zhang Guozhen^*

来源：International Journal of Computer Mathematics, 2014, 91(10): 2152-2162.

DOI：10.1080/00207160.2014.883069

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

A strongly connected digraph D is hyper-lambda 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-lambda digraph D to be m-hyper-lambda if D-S is still hyper-lambda for any arc set S with divide S divide <= m. The maximum integer of such m, denoted by H-lambda(D), is said to be the arc fault tolerance of D on the hyper-lambda property. H-lambda(D) is an index to measure the reliability of networks. In this paper, we study H-lambda(D) for the cartesian product digraph D=D(1)xD(2). We give a necessary and sufficient condition for D(1)xD(2) to be hyper-lambda and give the lower and upper bounds on H-lambda(D(1)xD(2)). An example shows that the lower and upper bounds are best possible. In particular, exact values of H-lambda(D(1)xD(2)) are obtained in special cases. These results are also generalized to the cartesian product of n strongly connected digraphs.

• 出版日期2014-10-3
• 单位山西大学