JCSE, vol. 12, no. 3, pp.115-126, 2018

DOI: http://dx.doi.org/10.5626/JCSE.2018.12.3.115

Paired Many-to-Many 3-Disjoint Path Covers in Bipartite Toroidal Grids

Jung-Heum Park
School of Computer Science and Information Engineering, The Catholic University of Korea, Bucheon, Korea

Abstract: Given two disjoint vertex-sets, S = {s1 ...,sk} and T = {t1 ..., tk} in a graph, a paired many-to-many k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths {Pi ...,Pk} that altogether cover every vertex of the graph, in which each path Pi runs from si to ti. 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 many-to-many 3-disjoint path cover joining S = {s1, s2, s3} and T = {t1, t2, t3} if and only if the set S U T contains the equal numbers of vertices from different parts of the bipartition.

Keyword: Disjoint path; Path cover; Path partition; Cylindrical grid; Torus

Full Paper:   247 Downloads, 1414 View