On 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 called a resolving partition if distinct vertices of $G$ have distinct representations. The minimum $k$ for which there is a resolving $k$-partition of $V(G)$ is the partition dimension $pd (G)$. If $pd (G) = k$, then $G$ is said to be $k$-dimensional. For every nontrivial connected graph $H$, we show that $pd (H) \leq pd (H \times K_2)$. We also show that for an induced subgraph $H$ of a connected graph $G$ the ratio $r_p = pd (H)/ pd (G)$ can be arbitrarily large. For every pair $k, n$ of integers with $2 \leq k \leq n$, it is shown that there exists a $k$-dimensional graph of order $n$. The $k$-dimensional trees are studied.