Paired Many-to-Many Disjoint Path Covers in Faulty Hypercubes

A paired many-to-many k-disjoint path cover (k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all the vertices of the graph. Extending the notion of DPC, we define a paired many-to-many bipartite k-DPC of a bipartite graph G to be a set of k disjoint paths joining k distinct source-sink pairs that altogether cover the same number of vertices as the maximum number of vertices covered when the source-sink pairs are given in the complete bipartite, spanning supergraph of G. We show that every m-dimensional hypercube, Qm, under the condition that f or less faulty elements (vertices and/or edges) are removed, has a paired many-to-many bipartite k-DPC joining any k distinct source-sink pairs for any f and k ≥ 1 subject to f + 2k ≤ m. This implies that Qm with m − 2 or less faulty elements is strongly Hamiltonian-laceable