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