On the strong metric dimension of corona product graphs and join graphs

DOI10.1016/J.DAM.2012.10.009zbMATH Open1262.05133arXiv1204.0495OpenAlexW2038288636WikidataQ57974335 ScholiaQ57974335MaRDI QIDQ1949107FDOQ1949107

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

Publication date: 25 April 2013

Published in: Discrete Applied 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. 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 $GodotH$, 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 $GodotH$ 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 $GodotH$ is obtained from the strong metric dimension of $K_{1}odotH$, where $K_1$ denotes the trivial graph. The strong metric dimension of join graphs is also studied.

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

zbMATH Keywords

clique numbercorona product graphstrong metric dimensionstrong metric basisstrong resolving setjoin graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• Metric dimension of some distance-regular graphs
• On the metric dimension of bilinear forms graphs
• On the metric dimension of Grassmann graphs
• Landmarks in graphs
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design
• Resolving domination in graphs
• The independent resolving number of a graph
• On Metric Generators of 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

Cited In (43)

• On the strong metric dimension of the strong products of graphs
• On the metric dimension of generalized tensor product of interval with paths and cycles
• On strong metric dimension of graphs and their complements
• On the strong partition dimension of graphs
• On the geodesic identification of vertices in convex plane graphs
• Strong resolving partitions for strong product graphs and Cartesian product graphs
• \(k\)-metric resolvability in graphs
• Closed formulae for the local metric dimension of corona product graphs
• On the strong metric dimension of Cartesian and direct products of graphs
• Hyperbolicity in the corona and join of graphs
• Resolvability and strong resolvability in the direct product of graphs
• The fractional strong metric dimension in three graph products
• Strong resolving graphs: the realization and the characterization problems
• On the metric dimension of corona product graphs
• On the local metric dimension of corona product graphs
• Simultaneous resolvability in families of corona product graphs
• The simultaneous strong metric dimension of graph families
• Adjacency and Laplacian spectra of variants of neighborhood corona of graphs constrained by vertex subsets
• Strong metric dimension in annihilating-ideal graph of commutative rings
• Geodesic transversal problem for join and lexicographic product of graphs
• Metric Dimension of Graph Join P2 and Pt
• Metric and strong metric dimension in cozero-divisor graphs
• Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\)
• Computing the strong metric dimension for co-maximal ideal graphs of commutative rings
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• On the strong metric dimension of annihilator graphs of commutative rings
• A short note on: there is no graph \(G\) with \(G_{\mathrm{SR}} \cong\)\(K_{r, s},\ r, s \geq 2\)
• The local complement metric dimension of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Closed formulae for the strong metric dimension of lexicographic product graphs
• THE STRONG CONNECTED METRIC DIMENSION IN THE JOIN AND CORONA OF GRAPHS
• Strong resolving graph of a zero-divisor graph
• Twin-free cliques in annihilator graphs of commutative rings
• Strong metric dimension of rooted product graphs
• Metric and strong metric dimension in commuting graphs of finite groups
• On the controllability of Corona product network
• Computing the \(k\)-metric dimension of graphs
• Fault-tolerant strong metric dimension of graphs
• Coloring, location and domination of corona graphs
• The strong metric dimension of the power graph of a finite group
• On dimension of some finite total graphs
• On the \(k\)-partition dimension of graphs

This page was built for publication: On the strong metric dimension of corona product graphs and join graphs

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