
doi: 10.3390/math8010125
handle: 10498/22719
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 ∈ V ( G ) are strongly resolved by a vertex w ∈ 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 ⊂ V is an SSMG for F , if such set S is a strong metric generator for every graph G ∈ F . The simultaneous strong metric dimension of F is the minimum cardinality of any strong metric generator for F , and is denoted by Sd s ( 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 Sd s ( F ) is described. That is, it is proved that computing Sd s ( 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.
QA1-939, simultaneous strong resolving set, Mathematics, simultaneous strong resolving graph, simultaneous strong metric dimension
QA1-939, simultaneous strong resolving set, Mathematics, simultaneous strong resolving graph, simultaneous strong metric dimension
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
