The Simultaneous Strong Metric Dimension of Graph Families

Let $$\mathcal{G}$$ be a family of graphs defined on a common (labelled) vertex set V. A set $$S\subset V$$ is said to be a simultaneous strong metric generator for $$\mathcal{G}$$ if it is a strong metric generator for every graph of the family. The minimum cardinality among all simultaneous strong metric generators for $$\mathcal{G}$$ , denoted by $${\text {Sd}}_s(\mathcal{G})$$ , is called the simultaneous strong metric dimension of $$\mathcal{G}$$ . We obtain general results on $${\text {Sd}}_s(\mathcal{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 $${\textit{NP}}$$ -hard, even when restricted to families of trees.