Unpaired Many-to-Many Disjoint Path Covers in Nonbipartite Torus-Like Graphs With Faulty Elements

One of the key problems in parallel processing is finding disjoint paths in the underlying graph of an interconnection network. The disjoint path cover of a graph is a set of pairwise vertex-disjoint paths that altogether cover every vertex of the graph. Given disjoint source and sink sets, $S = \{ s_{1},\ldots,s_{k}\}$ and $T = \{t_{1},\ldots, t_{k}\}$ , in graph $G$ , an unpaired many-to-many $k$ -disjoint path cover joining $S$ and $T$ is a disjoint path cover $\{ P_{1}, \ldots, P_{k}\}$ , in which each path $P_{i}$ runs from source $s_{i}$ to some sink $t_{j}$ . In this paper, we reveal that a nonbipartite torus-like graph, if built from lower dimensional torus-like graphs that have good disjoint-path-cover properties of the unpaired type, retains such a good property. As a result, an $m$ -dimensional nonbipartite torus, $m \geq 2$ , with at most $f$ vertex and/or edge faults has an unpaired many-to-many $k$ -disjoint path cover joining arbitrary disjoint sets $S$ and $T$ of size $k$ each, subject to $k \geq 1$ and $f+k \leq 2m-2$ . The bound of $2m-2$ on $f+k$ is nearly optimal