Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity

作     者：Tian, Zhaoxia Zhang, Mingzu Feng, Xing 

作者机构：Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Peoples R China Jiangxi Univ Sci & Technol Fac Sci Ganzhou 341000 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2022年第922卷

页      面：46-60页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Science and Technology Project of Xinjiang Uygur Autonomous Region [2020D01C069] National Natural Science Foundation of China [12101528, 12001250] Doctoral Startup Foundation of Xinjiang University Xinjiang Key Laboratory of Applied Mathematics [XJDX1401] Tianchi Ph.D Program [tebs201905] 

主　　题：h-extra edge-connectivity Concentration phenomenon Reliability and fault tolerance Parallel and distributed system Cartesian product lambda(h)-optimality 

摘      要：As a measurement parameter of the reliability about interconnection networks of parallel and distributed systems, the h-extra edge-connectivity lambda(h)(G) is a better alternative compared with the classical Menger s theorem of the edge-connectivity. Recently, Li and Yang (2013) [7] determined the values of the h- extra edge-connectivity of hypercube Q(n) for each h = 2(left perpendicularn/2right perpendicular). Because of easy scalability, the interconnection networks based on cartesianproduct operation are extensively investigated. This paper focuses on the h-extra edge-connectivity of the n-th cartesian product of complete graph K-4 with exponentially many faulty links. For a sufficiently large positive integer n, about 60 percent of positive integers hin the interval 1 = h = 2 . 4(n-1) corresponding h-extra edge-connectivity of K-4(n), lambda(h)(K-4(n)), presents a concentration phenomenon, that is, these exact values of lambda(h)(K-4(n)) concentrate on 3 . 4(n-1) and 4(n) for each inverted right perpendicular3 . 4n(-1)/5inverted left perpendicular = h = 4(n-1) and inverted right perpendicular6 . 4(n-1)/5inverted left perpendicular = h = 2 . 4(n-1), respectively. And the lower and upper bounds of hare sharp. Furthermore, the values of lambda(h)(K-2(n)) also have this phenomenon. We obtain lambda(h)(K-4(n)) = 3/2 lambda(h)(K-n2(2)) = 3 . 4(n-1) or lambda(h)( K-4(n)) = 2 lambda(h)(K-n2(2)) = 4(n) in the subintervals where the concentration phenomenon occurs simultaneously. (C) 2022 Elsevier B.V. All rights reserved.