The equidistant dimension of graphs (Q2147613)

In a graph \(G\), a vertex \(w\) is said to be equidistant from the vertices \(x\) and \(y\) if \(d(x, w) = d(y, w)\). A subset \(S\) of vertices is called a distance-equalizer set for \(G\) if for every two distinct vertices \(x, y \in V(G) \setminus S \), there exists a vertex \(w \in S\) equidistant from \(x\) and \(y\). The equidistant dimension of \(G\), denoted by \(\operatorname{eqdim}(G)\), is the minimum cardinality of a distance-equalizer set of \(G\). In this paper, the authors define these concepts and initially give bounds of equidistant dimension of \(G\) in terms of other graph parameters of \(G\), viz., the order, diameter, maximum degree, independence number, and clique number. Also, they characterize all nontrivial graphs achieving extremal values for the equidistant dimension, concretely, graphs \(G\) of order \(n \geq 2\) such that \(\operatorname{eqdim}(G) \in \{1, 2, n-2, n-1\}\). A Nordhaus-Gaddum-type inequality gives bounds on the sum or product of a parameter for a graph and its complement. In this paper, they provide a Nordhaus-Gaddum type bound on equidistant dimension by proving that, if \(G\) is a doubly connected graph of order \(n \geq 4\), then \(4 \leq\operatorname{eqdim}(G) +\operatorname{eqdim}(\bar{G}) \leq n + 1\). In the final sections of the paper, they study the equidistant dimension of several families of graphs (complete and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs). In particular, they prove that, in the case of paths and cycles, this parameter is related to 3-AP-free sets and \(r(n)\) introduced in [\textit{P. Erdős} and \textit{P. Turán}, J. Lond. Math. Soc. 11, 261--264 (1936; Zbl 0015.15203)]. A set \(S \subseteq V(G)\) is a doubly resolving set of \(G\) if every pair \(\{x, y\} \subseteq V(G)\) is doubly resolved by two vertices \(u\) and \(v\) in \(S\), that is, \(d(u, x) - d(u, y) \ne d(v, x) - d(v, y)\). This paper ends with obtaining some bounds for general graphs and trees on the minimum cardinality of doubly resolving sets in terms of the equidistant dimension. The conclusion of the paper includes some interesting open problems.