ISSN:
1420-8903
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Summary. 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00000127
Permalink