One-to-one disjoint path covers on multi-dimensional tori

摘要

The multi-dimensional torus is one of the most popular underlying topologies for massively parallel systems. In this study, we consider a non-bipartite n-dimensional torus where n >= 2 and prove that for 1 <= m <= 2n, m vertex disjoint paths exist that cover all vertices between any two distinct vertices. In other words, we construct the one-to-one m-disjoint path cover of a non-bipartite torus for any m where 1 <= m <= 2n.