The Simultaneous Strong Resolving Graph and the Simultaneous Strong Metric Dimension of Graph Families

Abstract

We consider in this work a new approach to study the simultaneous strong metric dimension of graphs families, while introducing the simultaneous version of the strong resolving graph. In concordance, we consider here connected graphs G whose vertex sets are represented as V(G), and the following terminology. Two vertices u,v is an element of V(G) are strongly resolved by a vertex w is an element of V(G), if there is a shortest w-v path containing u or a shortest w-u containing v. A set A of vertices of the graph G is said to be a strong metric generator for G if every two vertices of G are strongly resolved by some vertex of A. The smallest possible cardinality of any strong metric generator (SSMG) for the graph G is taken as the strong metric dimension of the graph G. Given a family F of graphs defined over a common vertex set V, a set S subset of V is an SSMG for F, if such set S is a strong metric generator for every graph G is an element of F. The simultaneous strong metric dimension of F is the minimum cardinality of any strong metric generator for F, and is denoted by Sds(F). The notion of simultaneous strong resolving graph of a graph family F is introduced in this work, and its usefulness in the study of Sds(F) is described. That is, it is proved that computing Sds(F) is equivalent to computing the vertex cover number of the simultaneous strong resolving graph of F. Several consequences (computational and combinatorial) of such relationship are then deduced. Among them, we remark for instance that we have proved the NP-hardness of computing the simultaneous strong metric dimension of families of paths, which is an improvement (with respect to the increasing difficulty of the problem) on the results known from the literature.