DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

P. Manuel

Title:

On the isometric path partition problem

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-01-29, Revised: 2019-05-14, Accepted: 2019-05-14, https://doi.org/10.7151/dmgt.2236

Abstract:

The isometric path cover (partition) problem of a graph consists of finding 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 of a minimum isometric path cover (partition). We prove that the isometric path partition problem and the isometric $k$-path partition problem for $k\geq 3$ are NP-complete on general graphs. Fisher and Fitzpatrick in [The isometric number of a graph, J. Combin. Math. Combin. Comput. 38 (2001) 97–110] have shown that the isometric path cover number of the $(r\times r)$-dimensional grid is $\lceil 2r/3\rceil$. We show that the isometric path cover (partition) number of the $(r\times s)$-dimensional grid is $s$ when $r \geq s(s-1)$. We establish that the isometric path cover (partition) number of the $(r\times 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 $2^r$. In addition, we provide partial solutions for the isometric path cover (partition) problems for cylinder and multi-dimensional grids. We apply two different techniques to achieve these results.

Keywords:

path cover problem, isometric path partition problem, isometric path cover problem, multi-dimensional grids, cylinder, torus

PDF
Close