On the strong metric generators of strong product graphs

arXiv1307.4724MaRDI QIDQ6243443FDOQ6243443

Authors: Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez 

Publication date: 17 July 2013

Abstract: Let $G$ be a connected graph. A vertex $winV(G)$ strongly resolves two vertices $u,vinV(G)$ if there exists some shortest $u-w$ path containing $v$ or some shortest $v-w$ path containing $u$. A set $S$ of vertices is a strong metric generator for $G$ if every pair of vertices of $G$ is strongly resolved by some vertex of $S$. The smallest cardinality of a strong metric generator for $G$ is called the strong metric dimension of $G$. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: On the strong metric generators of strong product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6243443)