Publication:5739613

DOI10.1080/00207160.2015.1061656zbMATH Open1342.05033arXiv1309.0643OpenAlexW1594561525WikidataQ57974192 ScholiaQ57974192MaRDI QIDQ5739613FDOQ5739613

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

Publication date: 19 July 2016

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Abstract: 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 of vertices of $G$ is strongly resolved by some vertex of $W$. The smallest cardinality of a strong resolving set for $G$ is called the strong metric dimension of $G$. It is known that the problem of computing this invariant is NP-hard. This suggests finding the strong metric dimension for special classes of graphs or obtaining good bounds on this invariant. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of rooted product of graphs and express these in terms of invariants of the factor graphs.

Full work available at URL: https://arxiv.org/abs/1309.0643

zbMATH Keywords

rooted product graphsstrong metric dimensionstrong metric basisstrong metric generator

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)

Cites Work

• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability and the upper dimension of graphs
• On the strong metric dimension of corona product graphs and join graphs
• Landmarks in graphs
• Metric bases in digital geometry
• On the strong metric dimension of Cartesian and direct products of graphs
• A new graph product and its spectrum
• Structure-activity maps for visualizing the graph variables arising in drug design
• On Metric Generators of Graphs
• A note on the partition dimension of Cartesian product graphs
• On the metric dimension of corona product graphs
• The strong metric dimension of graphs and digraphs
• Locating and total dominating sets in trees
• Conditional resolvability in graphs: a survey
• The partition dimension of a graph
• The partition dimension of Cayley digraphs
• Discrepancies between metric dimension and partition dimension of a connected graph
• On the metric dimension and fractional metric dimension for hierarchical product of graphs

Cited In (8)

• On the geodesic identification of vertices in convex plane graphs
• On metric dimensions of symmetric graphs obtained by rooted product
• Prime factorization and domination in the hierarchical product of graphs
• Spectra of M-rooted product of graphs
• Closed formulae for the strong metric dimension of lexicographic product graphs
• Edge metric dimensions via hierarchical product and integer linear programming
• Metric and strong metric dimension in commuting graphs of finite groups
• The strong metric dimension of the power graph of a finite group

This page was built for publication: Strong metric dimension of rooted product graphs

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