Paired Many-to-Many 3-Disjoint Path Covers in Bipartite Toroidal Grids
Jung-Heum Park · Journal of Computing Science and Engineering · 2018
Given two disjoint vertex-sets, S = {sSUB1/SUB, ...,sSUBk/SUB} and T = {tSUB1/SUB, ..., tSUBk/SUB} in a graph, a paired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {PSUB1/SUB, ...,PSUBk/SUB} that altogether cover every vertex of the graph, in which each path PSUBi/SUB runs from sSUBi/SUB to tSUBi/SUB. In this paper, we first study the disjoint-path-cover properties of a bipartite cylindrical grid. Based on the findings, we prove that every bipartite toroidal grid, excluding the smallest one, has a paired manyto- many 3-disjoint path cover joining S = {sSUB1/SUB, sSUB2/SUB, sSUB3/SUB} and T = {tSUB1/SUB, tSUB2/SUB, tSUB3/SUB} if and only if the set S ∪ T contains the equal numbers of vertices from different parts of the bipartition.