The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs

Let $V(G)$ be the vertex set of a simple and connected graph $G$. A subset $S\subseteq V(G)$ is a distance-equalizer set of $G$ if, for every pair of vertices $u,v\in V(G)\setminus S$, there exists a vertex in $S$ that is equidistant to $u$ and $v$. The minimum cardinality among the distance-equalizer sets of $G$ is the equidistant dimension of $G$, denoted by $\xi (G)$. In this paper, we studied the problem of finding $\xi (G\circ H)$, where $G\circ H$ denotes the lexicographic product of two graphs $G$ and $H$. The aim was to express $\xi (G\circ H)$ in terms of parameters of $G$ and $H$. In particular, we considered the cases in which $G$ has a domination number equal to one, as well as the cases where $G$ is a path or a cycle, among others. Furthermore, we showed that $\xi (G)\le \xi (G\circ H)\le \xi (G)|V(H)|$ for every connected graph $G$ and every graph $H$ and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.