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

Ismael González Yero
Additional contact information
Ismael González Yero: Departamento de Matemáticas, Universidad de Cádiz, EPS, 11202 Algeciras, Spain

Mathematics, 2020, vol. 8, issue 1, 1-11

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 ∈ 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.

Keywords: simultaneous strong resolving set; simultaneous strong metric dimension; simultaneous strong resolving graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/1/125/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/1/125/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:1:p:125-:d:308481

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().