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

Identifier:  imarina:9368593

Handle: https://hdl.handle.net/20.500.11797/imarina9368593

Authors:  Gispert-Fernandez, Adria; Rodriuez-Velazquez, Juan Alberto

Abstract:
Let V ( G ) be the vertex set of a simple and connected graph G . A subset S subset of V ( G ) is a distance -equalizer set of G if, for every pair of vertices u , v E 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 xi ( G ). In this paper, we studied the problem of finding xi ( G o H ), where G o H denotes the lexicographic product of two graphs G and H . The aim was to express xi ( G o 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 )