For an ordered set W = {w(1), w(2),..., w(k)} of vertices and a vertex v in
a connected graph G, the (metric) representation of v with respect to W is
the k-vector r(v\W) = (d(v, w(1)), d(v, w(2)),..., d(v, w(k))), where d(x,
y) represents the distance between the vertices x and y. The set W is a re
solving set for G if distinct vertices of G have distinct representations.
A new sharp lower bound for the dimension of a graph G in terms of its maxi
mum degree is presented.
A resolving set of minimum cardinality is a basis for G and the number of v
ertices in a basis is its (metric) dimension dim(G). A resolving set S of G
is a minimal resolving set if no proper subset of S is a resolving set. Th
e maximum cardinality of a minimal resolving set is the upper dimension dim
(+)(G). The resolving number res(G) of a connected graph G is the minimum I
c such that every k-set W of vertices of G is also a resolving set of G. Th
en 1 less than or equal to dim(G) less than or equal to dim(+) (G) less tha
n or equal to res(G) less than or equal to n - 1 for every nontrivial conne
cted graph G of order n. It is shown that dim+(G) = res(G) = n - 1 if and o
nly if G = K-n, while dim(+)(G) = res(G) = 2 if and only if G is a path of
order at least 4 or an odd cycle.
The resolving numbers and upper dimensions of some well-known graphs are de
termined. It is shown that for every pair a,b of integers with 2 less than
or equal to a less than or equal to b, there exists a connected graph G wit
h dim(G) = dim(+)(G) = a and res(G) = b. Also, for every positive integer N
, there exists a connected graph G with res(G) - dim(+)(G) greater than or
equal to N and dim(+)(G) - dim(G) greater than or equal to N. (C) 2000 Else
vier Science Ltd. All rights reserved.