Many-to-many edge-disjoint paths in (n, k)-enhanced hypercube under three link-faulty hypotheses

One of the most central issues in interconnection networks of parallel and distributed systems is finding edge-disjoint paths that transmit information. Finding as many as possible many-to-many edge-disjoint paths is conducive to improving the fault-tolerance of such networks. As an interconnection network topology, (n, k)-enhanced hypercube Qn,k (1 < k < n -1), is a momentous variant of well-known hypercube. For integers 1 < l < n -1 and n >= 2, let delta = 0 if 1 < l < n -k, and delta =1 if n -k + 1 < l < n -1. This paper offers a unified method to determine the minimum cardinalities of faulty links in Qn,k, whose malfunction divides this network into several connected components such that each processor has at least l + delta neighbors, each component contains no less than 2l processors and the number of average neighbors for all processors is at least l + delta, respectively. Under these three different link-faulty assumptions, but for the condition of k = 2 and l = n - 2, the minimum cardinalities of such faulty links share the same value (n - l - delta + 1)2l. And the value in the exceptional case is (n - l - delta)2l+1 = 2n-1. In other words, we find the maximum numbers of many-to-many edge-disjoint paths of Qn,k under the above three hypotheses, which offers refined measurements for the reliability and fault-tolerance of interconnection networks. (c) 2023 Elsevier B.V. All rights reserved.

Automated summary

One of the most important issues in interconnection networks is finding edge-disjoint paths that transmit information, and this paper offers a unified method to determine the minimum cardinalities of faulty links in a specific interconnection network topology. The minimum cardinalities of faulty links in this topology share the same value under different link-faulty assumptions, except for a specific case. The findings provide refined measurements for the reliability and fault-tolerance of interconnection networks.