- Tytuł:
- On the Isometric Path Partition Problem
- Autorzy:
- Manuel, Paul
- Powiązania:
- https://bibliotekanauki.pl/articles/32323579.pdf
- Data publikacji:
- 2021-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
path cover problem
isometric path partition problem
isometric path cover problem
multi-dimensional grids
cylinder
torus - Opis:
- 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 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 × r)-dimensional grid is ⌈2r/3 ⌉. We show that the isometric path cover (partition) number of the (r × s)-dimensional grid is s when r s(s − 1). We establish that the isometric path cover (partition) number of the (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. We apply two di erent techniques to achieve these results.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1077-1089
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł