کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419311 | 683778 | 2015 | 24 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 185, 20 April 2015, Pages 168–191