RT journal article
T1 On the strong metric dimension of corona product graphs and join graphs
A1 Kuziak, Dorota
A1 González Yero, Ismael
A1 Rodríguez Velázquez, J.A.
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 Strong metric dimension
K1 strong resolving set
K1 strong metric basis
K1 clique number
K1 corona product graph
K1 join graph
AB Let $G$ be a connected graph. A vertex $w$  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 strong resolving set for $G$ if every pair ofvertices of $G$ is strongly resolved by some vertex of $W$. The smallest cardinality of a strong resolving set for $G$ is called the strong metricdimension of $G$. It is known that the problem of computing this invariant is NP-hard. It is therefore desirable  to reduce the problem of computing the strong metric dimension of product graphs, to the problem of computing some parameter of the factor graphs. We show that the problem of finding the strong metric dimension of the corona product $G\odot H$, of two graphs $G$ and $H$, can be transformed to the problem of finding certain clique number of $H$. As a consequence of the study we show that if $H$ has diameter two, then the strong metric dimension of $G\odot H$ is obtained from the strong metric dimension of $H$ and, if $H$ is not connected or its  diameter is greater than two, then the strong metric dimension of $G\odot H$ is obtained from the strong metric dimension of $K_1\odot H$, where $K_1$ denotes the trivial graph. The strong metric dimension of join graphs is also studied.
PB Elsevier
SN 0166-218X
YR 2013
FD 2013-05
LK http://hdl.handle.net/10498/30922
UL http://hdl.handle.net/10498/30922
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026