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.