Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity

Zhang, Guozhen  ; Wang, Shiying

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 95-116

Résumé

Let D = (V (D),A(D)) be a strongly connected digraph. An arc set S ⊆ A(D) is a restricted arc-cut of D if D − S has a non-trivial strong component D_1 such that D − V (D_1) contains an arc. The restricted arc-connectivity λ^‘(D) is the minimum cardinality over all restricted arc-cuts of D. In [C. Balbuena, P. García-Vázquez, A. Hansberg and L.P. Montejano, On the super-restricted arc-connectivity of s-geodetic digraphs, Networks 61 (2013) 20-28], Balbuena et al. introduced the concept of super-λ^' digraphs. In this paper, we first introduce the concept of the arc fault tolerance of a digraph D on the super-λ^‘ property. We define a super-λ^′ digraph D to be m-super-λ^‘ if D − S is still super-λ^‘ for any S ⊆ A(D) with |S| ≤ m. The maximum value of such m, denoted by S_λ^’ (D), is said to be the arc fault tolerance of D on the super-λ^‘ property. S_λ^’ (D) is an index to measure the reliability of networks. Next we provide a necessary and sufficient condition for the Cartesian product of regular digraphs to be super-λ^‘. Finally, we give the lower and upper bounds on S_λ^’ (D) for the Cartesian product D of regular digraphs and give an example to show that the lower and upper bounds are best possible. In particular, the exact value of S_λ^’ (D) is obtained in special cases.

Détail

Keywords: fault tolerance, restricted arc-connectivity, super-restricted arc- connectivity, Cartesian product, regular digraph