Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs

For two disjoint vertex-sets, S = {s(1), ... ,s(k)) and T = {t(1), ..., t(k)} of a graph, an unpaired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {P-1, ..., P-k} that altogether cover every vertex of the graph, in which P-i is a path from si to some t(j) for 1 <= i, j <= k. A family of hypercube-like interconnection networks, called restricted hypercube-like graphs, includes most nonbipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Mobius cubes, recursive circulant G(2(m), 4) of odd m, etc. In this paper, we show that every m-dimensional restricted hypercube-like graph, m >= 5, with at most f faulty vertices and/or edges being removed has an unpaired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each subject to k >= 2 and f + k <= m - 1. The bound m - 1 on f + k is the maximum possible. (C) 2016 Elsevier B.V. All rights reserved.