2018/08/26 by Manuel, Paul · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.09097
The isometric path cover (partition) problem of a graph is to find a minimum set of isometric paths which cover (partition) the vertex set of the graph. The isometric path cover (partition) number of a graph is the cardinality a minimum isometric path cover (partition). We prove that the isometric path partition problem and the isometric k-path partition problem for k≥ 3 are NP-complete on general graphs. Fisher and Fitzpatrick \citeFiFi01 have shown that the isometric path cover number of (r× r)-dimensional grid is \lceil 2r/3\rceil. We show that the isometric path cover (partition) number of (r× s)-dimensional grid is s when r ≥ s(s-1). We establish that the isometric path cover (partition) number of (r× r)-dimensional torus is r when r is even and is either r or r+1 when r is odd. Then, we demonstrate that the isometric path cover (partition) number of an r-dimensional Benes network is 2r. In addition, we provide partial solutions for the isometric path cover (partition) problems for cylinder and multi-dimensional grids.