The Partition Dimension of a Graph



For a vertex $v$ of a connected graph $G$ and a subset $S$ of $V(G)$, the distance between $v$ and $S$ is $d(v, S) = \min \{d(v, x) | x \in S\}$. For an ordered $k$-partition $\Pi = \{S_1, S_2, \cdots, S_k\}$ of $V(G)$, the representation of $v$ with respect to $\Pi$ is the $k$-vector $r(v | \Pi)$ $=$ ($d(v, S_1),$ $d(v, S_2),$ $\cdots,$ $d(v, S_k)$). The $k$-partition $\Pi$ is a resolving partition if the $k$-vectors $r(v | \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 $pd (G)$ of $G$. It is shown that the partition dimension of a graph $G$ is bounded above by 1 more than its metric dimension. An upper bound for the partition dimension of a bipartite graph $G$ is given in terms of the cardinalities of its partite sets, and it is shown that the bound is attained if and only if $G$ is a complete bipartite graph. Graphs of order $n$ having partition dimension 2, $n$, or $n-1$ are characterized