2013/07/17 by Rodríguez-Velázquez, Juan A., Yero, Ismael G., Kuziak, Dorota +1 · 1 citation
#05C12 #05C76 #05C90 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1307.4722
Let G be a connected graph. A vertex w \em strongly resolves a pair u, v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a \em strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the \em strong metric dimension of G. It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian product graphs and direct product graphs.