Paired many-to-many disjoint path covers in faulty hypercubes

Abstract

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, Q(m), 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 Q(m) with m - 2 or less faulty elements is strongly Hamiltonian-laceable.