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 ∈ S}. For an ordered k-partition Π = {S1,S2, ⋯, Sk} of V(G), the representation of v with respect to Π is the k-vector r(v|Π) = (d(v, S1), d(v, S2), ⋯, d(v, Sk)). The k-partition Π is a resolving partition if the k-vectors r(v|Π), v ∈ 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. © Birkhäuser Verlag, Basel, 2000.