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

A many-to-many k-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₀ ⊕ G₁ obtained from connecting two graphs G₀ and G₁ with n vertices each by n pairwise nonadjacent edges joining vertices in G₀ and vertices in G₁. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G₀ ⊕ G₁ connecting two lower dimensional networks G₀ and G₁. In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G₀ ⊕ G₁ and (G₀ ⊕ G₁) ⊕ (G₂ ⊕ G₃ ), 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 subclasses 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.