그래프의 쌍형 다대다 k-서로소인 경로 커버 (k-DPC)는 k개의 서로 다른 소스-싱크 쌍을 연결하면서 그래프에 있는 모든 정점을 지나는 k개의 서로소인 경로 집합을 말한다. 2-차원 $m{ imes}n$ 토러스는 길이가 각각 m과 n인 두 사이클 $C_m$과 $C_n$의 곱으로 정의되는 그래프이다. 이 논문은 고장 정점을 하나 가진 $m{ imes}n$ 이분 토러스(짝수 $m,n{geq}4$)를 고려하여, 다음과 같이 이 토러스가 주어진 두 소스-싱크 쌍을 잇는 쌍형 다대다 2-DPC를 가질 필요충분조건을 제시한다: 네 개의 소스와 싱크 중에서 정확히 하나가 고장 정점과 같은 색이다.
A paired many-to-many k-disjoint path cover (k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of the graph is covered by a path. A two-dimensional $m{ imes}n$ torus is a graph defined as the product of two cycles $C_m$ and $C_n$ of length m and n, respectively. In this paper, we deal with an $m{ imes}n$ bipartite torus, even $m,n{geq}4$, with a single faulty vertex, and present a necessary and sufficient condition for the torus to have a paired many-to-many 2-DPC connecting given two source-sink pairs as follows: Out of the four sources and sinks, exactly one of them has the same color as the faulty vertex.
