On Path Partition Dimension of Trees

Abstract

For a connected graph \(G\) and any two vertices \(u\) and \(v\) in \(G\), let \(d(u,v)\) denote the distance between \(u\) and \(v\) and let \(d(G)\) be the diameter of \(G\). For a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v, S) = \min\{d(v,x) \mid x \in S\}\). Let \(\Pi = \{S_1, S_2, \ldots, S_k\}\) be an ordered \(k\)-partition of \(V(G)\). The representation of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(r(v \mid \Pi) = (d(v, S_1), d(v, S_2), \ldots, d(v, S_k))\). A partition \(\Pi\) is a resolving partition for \(G\) if the \(k\)-vectors \(r(v \mid \Pi)\), \(v \in V(G)\) are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is the partition dimension of \(G\), and is denoted by \(pd(G)\). A partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) is a resolving path \(k\)-partition for \(G\) if it is a resolving partition and each subgraph induced by \(S_i\), \(1 \leq i \leq k\), is a path. The minimum \(k\) for which there exists a path resolving \(k\)-partition of \(V(G)\) is the path partition dimension of \(G\), denoted by \(ppd(G)\). In this paper, path partition dimensions of trees and the existence of graphs with given path partition, partition, and metric dimension, respectively, are studied.