# zbMATH — the first resource for mathematics

On $$k$$-dimensional graphs and their bases. (English) Zbl 1026.05033
For an order set $$W=\{w_1,w_2,\dots,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),\dots,d(v,w_k))$$, where $$d(x, y)$$ denotes 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 of minimum cardinality $$k$$ is called a basis for $$G$$ and $$k$$ is its dimension. (The inspiration for this topic stems from chemistry.) The authors investigate how the dimension of a connected graph can be affected by the addition of a vertex, and they present a formula for the dimension of a wheel. Furthermore, it is shown that for every integer $$k\geq 2$$, there exists a $$k$$-dimensional graph with a unique basis, and that for every pair $$r$$, $$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$$.

##### MSC:
 05C12 Distance in graphs
##### Keywords:
resolving set; dimension; basis
Full Text: