Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity
复制标题
DOI：
10.1016/j.tcs.2022.04.010
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Zhaoxia Tian;Mingzu Zhang;Xing Feng
中科院分区：
文献类型：
--
作者：
Zhaoxia Tian;Mingzu Zhang;Xing Feng
作为并行分布系统互连网络可靠性的度量参数，h-额外边连通度λ h（G）是一个比经典的边连通度Menger定理更好的选择。最近，Li和Yang（2013）[7]确定了超立方体Qn的h-额外边连通度的值，其中h≤ 2 <$n 2 <$。基于乘积运算的互连网络因其易于扩展而得到广泛研究。本文重点研究具有指数级错误链接的完全图K4的第n阶笛卡尔积的h-额外边连通性。对于一个足够大的正整数n，在1≤ h≤ 2 <$4n − 1区间内约60%的正整数h对应的K4 n的h-额外边连通性λ h（K4 n）呈现集中现象，即λ h（K 4 n）的精确值分别集中在3 <$4 n− 1和4 n上，分别对应于每个<$3 <$4 n− 1/5 <$$> ≤ h≤ 4 n− 1和<$6 <$4 n− 1。而h的上界和下界都很尖锐。此外，λ h（K2 n）的值也有这种现象.在集中现象同时发生的子区间中，得到λ h（K4 n）= 3 2 λ h（K2 2 n）= 3 <$4 n− 1或λ h（K4 n）= 2 λ h（K2 2 n）= 4 n.
As a measurement parameter of the reliability about interconnection networks of parallel and distributed systems, the h-extra edge-connectivity λ 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⌊ n 2⌋. Because of easy scalability, the interconnection networks based on cartesian product 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 h in the interval 1≤ h≤ 2⋅ 4 n− 1 corresponding h-extra edge-connectivity of K 4 n, λ h (K 4 n), presents a concentration phenomenon, that is, these exact values of λ h (K 4 n) concentrate on 3⋅ 4 n− 1 and 4 n for each⌈ 3⋅ 4 n− 1/5⌉≤ h≤ 4 n− 1 and⌈ 6⋅ 4 n− 1/5⌉≤ h≤ 2⋅ 4 n− 1, respectively. And the lower and upper bounds of h are sharp. Furthermore, the values of λ h (K 2 n) also have this phenomenon. We obtain λ h (K 4 n)= 3 2 λ h (K 2 2 n)= 3⋅ 4 n− 1 or λ h (K 4 n)= 2 λ h (K 2 2 n)= 4 n in the subintervals where the concentration phenomenon occurs simultaneously.