Torus-like graphs and their paired many-to-many disjoint path covers

Given two disjoint vertex-sets, S = {s(1), ..., s(k)} and T = {t(1), ..., t(k)} in a graph, a paired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {P-1, ...,P-k} that altogether cover every vertex of the graph, in which each path P-i runs from s(i) to t(i). In this paper, we propose a family of graphs, called torus-like graphs, that include torus networks, and reveal that a torus-like graph, if built from lower dimensional torus-like graphs that have good Hamiltonian and disjoint-path-cover properties, retain such good properties. As a result, every m-dimensional nonbipartite torus, m >= 2, with at most f vertex and/or edge faults has a paired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each, subject to k >= 2 and f + 2k <= 2m. The bound 2m on f + 2k is nearly optimal. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces a class of torus-like graphs and demonstrates that building torus-like graphs from lower dimensional ones with good properties will retain these properties. Therefore, for every m-dimensional nonbipartite torus, m >= 2, with at most f vertex and/or edge faults, there exists a paired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each.