On the partition dimension of trees

Abstract

Given an ordered partition $\Pi =\{P_1,P_2,...,P_t\}$ of the vertex set $V$ of a connected graph $G=(V,E)$, the \emph{partition representation} of a vertex $v\in V$ with respect to the partition $\Pi$ is the vector $r(v|\Pi )=(d(v,P_1),d(v,P_2),...,d(v,P_t))$, where $d(v,P_i)$ represents the distance between the vertex $v$ and the set $P_i$. A partition $\Pi$ of $V$ is a \emph{resolving partition} of $G$ if different vertices of $G$ have different partition representations, i.e., for every pair of vertices $u,v\in V$, $r(u|\Pi )\ne r(v|\Pi )$. The \emph{partition dimension} of $G$ is the minimum number of sets in any resolving partition of $G$. In this paper we obtain several tight bounds on the partition dimension of trees.

References in corpus (1)

• A note on the partition dimension of Cartesian product graphs

Cited by in corpus (3)

• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• Partition dimension and strong metric dimension of chain cycle
• The Neighbor-Locating-Chromatic Number of Pseudotrees