One-to-many disjoint path covers in a graph with faulty elements

Abstract. In a graph G, k vertex disjoint paths joining k distinct sourcesink pairs that cover all the vertices in the graph are called a many-tomany k-disjoint path cover(k-DPC) of G. We consider an f-fault k-DPC problem that is concerned with finding many-to-many k-DPC in the presence of f or less faulty vertices and/or edges. We consider the graph obtained by merging two graphs H0 and H1, |V (H0) | = |V (H1) | = n, with n pairwise nonadjacent edges joining vertices in H0 and vertices in H1. We present sufficient conditions for such a graph to have an f-fault k-DPC and give the construction schemes. Applying our main result to interconnection graphs, we observe that when there are f or less faulty elements, all of recursive circulant G(2 m, 4), twisted cube T Qm, and crossed cube CQm of degree m have f-fault k-DPC for any k ≥ 1 and f ≥ 0 such that f + 2k ≤ m − 1.