On the metric representation of the vertices of a graph

Abstract

The metric representation of a vertex $u$ in a connected graph $G$ respect to an ordered vertex subset $W=\{{\omega }_1,\dots ,{\omega }_n\}\subset V(G)$ is the vector of distances $r(u|W)=(d(u,{\omega }_1),\dots ,d(u,{\omega }_n))$. A vertex subset $W$ is a resolving set of $G$ if $r(u|W)\ne r(v|W)$, for every $u,v\in V(G)$ with $u\ne v$. Thus, a resolving set with $n$ elements provides a set of metric representation vectors $S\subset {\mathbb{Z}}^n$ with cardinal equal to the order of the graph. In this paper, we address the reverse point of view, that is, we characterize the finite subsets $S\subset {\mathbb{Z}}^n$ that are realizable as the set of metric representation vectors of a graph $G$ with respect to some resolving set $W$. We also explore the role that the strong product of paths plays in this context. Moreover, in the case $n=2$, we characterize the sets $S\subset {\mathbb{Z}}^2$ that are uniquely realizable as the set of metric representation vectors of a graph $G$ with respect to a resolving set $W$.