Many-to-Many Disjoint Path Covers in Two-Dimensional Tori
Jung-Heum Park · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2009
A paired many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. A two-dimensional torus is a graph defined as a product of two cycles and of length m and n, respectively. In this paper, we show that an torus with and odd has a 2-DPC joining any two source-sink pairs of vertices. This result is optimal in a sense that an torus does not always have a 3-DPC and that the graph with one faulty vertex or edge does not always have a 2-DPC.