The Simultaneous Strong Metric Dimension of Graph Families

Abstract

Let $\mathcal{G}$ be a family of graphs defined on a common (labeled) 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 $S{d}_s(\mathcal{G})$, is called the simultaneous strong metric dimension of $\mathcal{G}$. We obtain general results on $S{d}_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 $NP$-hard, even when restricted to families of trees.

arXiv admin note: text overlap with arXiv:1312.1987 by other authors

References in corpus (1)

• The Simultaneous Metric Dimension of Graph Families