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.$