The metric dimension of strong product graphs

Abstract

For an ordered subset $S=\{s_1,s_2,\dots s_k\}$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $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. 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.

Cited by in corpus (1)

• Metric Dimension of Amalgamation of Graphs