ON k-DIMENSIONAL GRAPHS AND THEIR BASES

For an ordered set W = {w₁, w₂,.… 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₁), d(v, w₂), …, d(v, w_k, where d(x, y) represents the distance between the vertices x and y. The set W is 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 ≥ 2, there exists a k-dimensional graph with a unique basis and that for every pair r and k of inegers with k ≥ 2 and 0 ≤ r ≤ k, there exists a k-dimensional graph G such that there are exactly r vertices that belong to every basis of G.