Many-to-Many Disjoint Path Covers in the Presence of 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 sources and k sinks in which each vertex of G is covered by a path. It is called a paired many-to-many disjoint path cover when each source should be joined to a specific sink, and it is called an unpaired many-to-many disjoint path cover when each source can be joined to an arbitrary sink. In this paper, we discuss about paired and unpaired many-to-many disjoint path covers including their relationships, application to strong Hamiltonicity, and necessary conditions. And then, we give a construction scheme for paired many-to-many disjoint path covers in the graph H₀ oplus H₁ obtained from connecting two graphs H₀ and H₁ with |V(H₀)| = |V(H₁)| by |V(H₁)| pairwise nonadjacent edges joining vertices in H₀ and vertices in H₁, where H₀ = G₀ oplus G₁ and H₁ = G₂ oplus G₃ for some graphs G_j. Using the construction, we show that every m-dimensional restricted HL-graph and recursive circulant G(2^m, 4) with f or less faulty elements have a paired k-DPC for any f and k ges 2 with f + 2k les m.