Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements

A many-to-many-to-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G(0) circle plus G(1) obtained from connecting two graphs G(0) and G(1) with n vertices each by n pairwise nonadjacent edges joining vertices in G(0) and vertices in G(1). Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G(0) circle plus G(1) connecting two lower dimensional networks G(0) and G(1). In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G(0) circle plus G(1) and (G(0) circle plus G(1)) circle plus (G(2) circle plus G(3)), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G(i) are satisfied, 0 <= i <= 3. We apply our main results to recursive circulant G(2(m),4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclass includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k; >= 1 and f >= 0 such that f + 2k: <= m - 1.