Many-to-many two-disjoint path covers in cylindrical and toroidal grids

A many-to-many kk-disjoint path cover of a graph joining two disjoint vertex sets SS and TT of equal size kk is a set of kk vertex-disjoint paths between SS and TT that altogether cover every vertex of the graph. The many-to-many kk-disjoint path cover is classified as paired if each source in SS is further required to be paired with a specific sink in TT, or unpaired otherwise. In this paper, we first establish a necessary and sufficient condition for a bipartite cylindrical grid to have a paired many-to-many 22-disjoint path cover joining SS and TT. Based on this characterization, we then prove that, provided the set S∪TS∪T contains the equal numbers of vertices from different parts of the bipartition, the bipartite cylindrical grid always has an unpaired many-to-many 22-disjoint path cover. Additionally, we show that such balanced vertex sets also guarantee the existence of a paired many-to-many 22-disjoint path cover for any bipartite toroidal grid even if an arbitrary edge is removed.