2013/07/17 by Dorota Kuziak, Kuziak, Dorota, Ismael G. Yero +4
Computer Science · Mathematics · #05C12 #05C69 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C12 #msc:05C69 #msc:05C76
paper · pdf · doi:10.48550/arxiv.1307.4724
12 pages
arxiv created 2013/07/17 · openalex publication_date 2013/07/17 · arxiv updated 2013/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph. A vertex w∈ V(G) strongly resolves two vertices u,v∈ V(G) if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.