Geodesic
Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 95-116.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: fault tolerance, restricted arc-connectivity, super-restricted arc- connectivity, Cartesian product, regular digraph 
@article{DMGT_2019_39_1_a8,
     author = {Zhang, Guozhen and Wang, Shiying},
     title = {Arc {Fault} {Tolerance} of {Cartesian} {Product} of {Regular} {Digraphs} on {Super-Restricted} {Arc-Connectivity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {95--116},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a8/}
}
TY  - JOUR
AU  - Zhang, Guozhen
AU  - Wang, Shiying
TI  - Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 95
EP  - 116
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a8/
LA  - en
ID  - DMGT_2019_39_1_a8
ER  - 
%0 Journal Article
%A Zhang, Guozhen
%A Wang, Shiying
%T Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 95-116
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a8/
%G en
%F DMGT_2019_39_1_a8
Zhang, Guozhen; Wang, Shiying. Arc Fault Tolerance of Cartesian Product of Regular Digraphs on Super-Restricted Arc-Connectivity. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 95-116. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a8/

[1] D. Bauer, F. Boesch, C. Suffel and R. Tindell, Combinatorial optimization problems in the analysis and design of probabilistic networks, Networks 15 (1985) 257-271. doi: 10.1002/net.3230150210

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000).

[3] 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. doi: 10.1002/net.21462

[4] C.W. Cheng and S.Y. Hsieh, Bounds for the super extra edge connectivity of graphs, in: International Computing and Combinatorics Conference, D. Xu, D. Du, D. Du (Ed(s)), Lecture Notes in Comput. Sci. 9198 (2015) 624-631. doi: 10.1007/978-3-319-21398-9 49

[5] X. Chen, J. Liu and J. Meng, The restricted arc connectivity of Cartesian product digraphs, Inform. Process. Lett. 109 (2009) 1202-1205. doi: 10.1016/j.ipl.2009.08.005

[6] A.H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195-199. doi: 10.1016/0020-0190(88)90025-7

[7] Y. Hong, J. Meng and Z. Zhang, Edge fault tolerance of graphs with respect to super edge connectivity, Discrete Appl. Math. 160 (2012) 579-587. doi: 10.1016/j.dam.2011.10.033

[8] Z.M. Hong and J.M. Xu, Vulnerability of super edge-connected networks, Theoret. Comput. Sci. 520 (2014) 75-86. doi: 10.1016/j.tcs.2013.10.021

[9] J. Liu and J. Meng, Super-connected and super-arc-connected Cartesian product of digraphs, Inform. Process. Lett. 108 (2008) 90-93. doi: 10.1016/j.ipl.2008.04.006

[10] J. Liu, J. Meng and Z. Zhang, Double-super-connected digraphs, Discrete Appl. Math. 158 (2010) 1012-1016. doi: 10.1016/j.dam.2010.02.004

[11] L. Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett. 103 (2007) 234-239. doi: 10.1016/j.ipl.2007.04.004

[12] S. Wang and S. Lin, λ′-optimal digraphs, Inform. Process. Lett. 108 (2008) 386-389. doi: 10.1016/j.ipl.2008.07.008

[13] J.M. Xu, Connectivity of Cartesian product digraphs and fault-tolerant routings of generalized hypercubes, Appl. Math. J. Chinese Univ. 13 (1998) 179-187. doi: 10.1007/s11766-998-0039-x

[14] J.M. Xu, Topological Structure and Analysis of Interconnection Networks (Kluwer Academic Publishers, Dordrecht, 2001). doi: 10.1007/978-1-4757-3387-7

[15] C. Yang and J.M. Xu, Reliability of interconnection networks modeled by Cartesian product digraphs, Networks 52 (2008) 202-205. doi: 10.1002/net.20231

[16] G. Zhang, Arc fault tolerance of Cartesian product digraphs on hyper arc connectiv- ity, Int. J. Comput. Math. 91 (2014) 2152-2162. doi: 10.1080/00207160.2014.883069

[17] Z. Zhang and Y. Zhu, Cyclic arc-connectivity in a Cartesian product digraph, Appl. Math. Lett. 23 (2010) 796-800. doi: 10.1016/j.aml.2010.03.013.