@article{Gispert-Fernández2024, 
author = {Adrià Gispert-Fernández and Juan Alberto Rodríguez-Velázquez},
title = {The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs},
year = {2024},
journal = {AIMS Mathematics},
volume = {9},
number = {6},
pages = {15325-15345},
keywords = {equidistant dimension, distance-equalizer, lexicographic product, NP-complete problem, distances in graphs},
url = {https://www.sciopen.com/article/10.3934/math.2024744},
doi = {10.3934/math.2024744},
abstract = {Let    V  (  G  ) be the vertex set of a simple and connected graph    G. A subset    S  ⊆  V  (  G  ) is a distance-equalizer set of    G if, for every pair of vertices    u  ,  v  ∈  V  (  G  )  ∖  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    ξ  (  G  ). In this paper, we studied the problem of finding    ξ  (  G  ∘  H  ), where    G  ∘  H denotes the lexicographic product of two graphs    G and    H. The aim was to express    ξ  (  G  ∘  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    ξ  (  G  )  ≤  ξ  (  G  ∘  H  )  ≤  ξ  (  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.}
}