On K-Dimensional Graphs and Their Bases



For an ordered set $W=\{w_1, w_2, \cdots, w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the ordered $k$-tuple $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 every two vertices of $G$ have distinct representations. A resolving set containing a minimum number of vertices is called a basis for $G$ and the number of vertices in a basis is its dimension $\dim(G)$. If $\dim(G) = k$, then $G$ is said to be $k$-dimensional. We investigate how the dimension of a connected graph can be affected by the addition of a single vertex. A formula is developed for the dimension of a wheel. It is shown that for every integer $k \geq2$, there exists a $k$-dimensional graph with a unique basis and that for every pair $r$ and $k$ of integers with $k \geq 2$ and $0 \leq r \leq k$, there exists a $k$-dimensional graph $G$ such that there are exactly $r$ vertices that belong to every basis of $G$.