RT journal article
T1 The metric dimension of strong product graphs
A1 Rodríguez Velázquez, Juan A.
A1 Kuziak, Dorota
A1 González Yero, Ismael
A1 Sigarreta Almira, José M.
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 Metric generator
K1 metric basis
K1 metric dimension
K1 strong product graph
K1 resolving set
AB 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.
SN 1584-2851
YR 2015
FD 2015-06-30
LK http://hdl.handle.net/10498/30930
UL http://hdl.handle.net/10498/30930
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026