The Simultaneous Strong Metric Dimension of Graph Families

Identifier:  PC:1785

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

Authors:  C. García-Gómez; A. Estrada-Moreno; Y. Ramírez-Cruz; J. A. Rodríguez-Velázquez

Abstract:
Let G be a family of graphs defined on a common (labelled) vertex set V. A set S¿ V is said to be a simultaneous strong metric generator for G if it is a strong metric generator for every graph of the family. The minimum cardinality among all simultaneous strong metric generators for G, denoted by Sd s(G) , is called the simultaneous strong metric dimension of G. We obtain general results on Sd s(G) for arbitrary families of graphs, with special emphasis on the case of families composed by a graph and its complement. In particular, it is shown that the problem of finding the simultaneous strong metric dimension of families of graphs is NP-hard, even when restricted to families of trees.