The metric dimension of strong product graphs

Rodríguez-Velázquez, Juan A., Kuziak, Dorota, Yero, Ismael G. and Sigarreta, José M.

Abstract

carpathian_2015_31_2_261_268_abstract

Full PDF

carpathian_2015_31_2_261_268

Issue no: Vol 31/2015 no. 2 Tags: Metric basis, Metric dimension, Strong product graph, Resolving set, Metric generator

Description
Additional information

For an ordered subset $S = \{s_1, s_2,\dots s_k\}$ of vertices in a connected graph $G$ , the metric representation of a vertex $u$ with respect to the set $S$ is the $k$ -vector $r(u|S)=(d_G(v,s_1), d_G(v,s_2),\dots,$ $d_G(v,s_k))$ , where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$ . The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations with respect to $S$ . A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$ , the metric dimension of $G$ . It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.