Resolvability and the Upper Dimension of Graphs
For an ordered set $W=\{w_1, w_2, \cdots, 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), $ $ \cdots,$ $ d(v, w_k)$),
where $d(x,y)$ represents the distance between the vertices $x$ and $y$.
The set $W$ is a resolving 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 maximum degree
is presented.
A resolving set of minimum cardinality
is a basis for $G$ and the number of vertices 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.
The 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 $k$ such that every $k$-set $W$ of vertices of $G$
is also a resolving set of $G$. Then
$1 \leq \dim (G) \leq \dim^+ (G) \leq \res (G) \leq n-1$ for
every nontrivial connected graph $G$ of order $n$.
It is shown that $\dim^+ (G) = \res(G) = n-1$ if and only 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 determined.
It is shown that
for every pair $a, b$ of integers with $2 \leq a \leq b$, there exists
a connected graph $G$ with $\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) \geq N$ and $\dim^+ (G) - \dim (G)\geq N.$