On the metric representation of the vertices of a graph (Q6056696)

Let \(G\) be a connected graph with vertex set \(V(G)\) and let \(d(u,w)\) denote the minimum number of edges connecting vertices \(u\) and \(w\) in \(G\). For an ordered set \(S=\{u_1, u_2, \ldots, u_k\}\subseteq V(G)\), the metric code of a vertex \(w\in V(G)\) with respect to \(S\), denoted by \(\operatorname{code}_G(w,S)\), is the \(k\)-vector \((d(w, u_1), d(w, u_2), \ldots, d(w, u_k))\). A set \(S\subseteq V(G)\) is a resolving set of \(G\) if, for any pair of distinct vertices \(x,y\in V(G)\), there exists \(z\in S\) such that \(d(x,z)\neq d(y,z)\). A set \(S\subseteq V(G)\) is a strong resolving set of \(G\) if, for any pair of distinct vertices \(x,y\in V(G)\), there exists \(z\in S\) such that either \(x\) lies on a shortest \(y-z\) path or \(y\) lies on a shortest \(x-z\) path in \(G\). \textit{A. Sebö} and \textit{E. Tannier} [Math. Oper. Res. 29, No. 2, 383--393 (2004; Zbl 1082.05032)] provide an example showing that there exist non-isomorphic graphs \(G_1\) and \(G_2\) on a common vertex set \(V\) with a common resolving set \(S\subseteq V\) such that \(\operatorname{code}_{G_1}(w, S)=\operatorname{code}_{G_2}(w, S)\) for each vertex \(w\in V\). On the other hand, Sebö and Tannier [loc. cit.] state that if \(S\) is a strong resolving set of a graph, the collection \(\{\operatorname{code}_G(w, S): w\in V(G)\}\) uniquely determines a graph \(G\); a proof for this claim is provided by \textit{C. X. Kang} and \textit{E. Yi} [Lect. Notes Comput. Sci. 8287, 84--95 (2013; Zbl 1407.05078)]. The authors of the current paper attempt to answer the following questions: \begin{itemize} \item[(1)] Is a finite subset \(\mathcal{C} \subseteq \mathbb{Z}^n\) realizable as a set of metric codes of a graph \(G\) with respect to a resolving set \(S\)? \item[(2)] If the set \(\mathcal{C}\subseteq \mathbb{Z}^n\) is realizable, does \(\mathcal{C}\) uniquely determine a graph? \end{itemize} The authors provide an answer to (1) by characterizing the conditions for which \(\{\operatorname{code}_G(w, S): w\in V(G)\}\) is a realizable set of a graph with respect to a resolving \(S\). Regarding (2), the authors characterize the collection \(\mathcal{C}=\{\operatorname{code}_G(w, S): w\in V(G)\}\) that are uniquely realizable when \(|S|=2\).