Computing the metric dimension of a graph from primary subgraphs

DOI10.7151/DMGT.1934zbMATH Open1354.05040arXiv1309.0641OpenAlexW2962805334WikidataQ57974177 ScholiaQ57974177MaRDI QIDQ503686FDOQ503686

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

Publication date: 23 January 2017

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: Let $G$ be a connected graph. Given an ordered set $W=w_1,w_2,dots{w}_{k}subseteqV(G)$ and a vertex $uinV(G)$, the representation of $u$ with respect to $W$ is the ordered $k$-tuple $(d(u,w_1),d(u,w_2),dots,$ $d(u,w_k))$, where $d(u,w_i)$ denotes the distance between $u$ and $w_i$. The set $W$ is a metric generator for $G$ if every two different vertices of $G$ have distinct representations. A minimum cardinality metric generator is called a emph{metric basis} of $G$ and its cardinality is called the emph{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 for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.

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

Recommendations

• Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs
• Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components
• The metric dimension of strong product graphs
• Computing the \(k\)-metric dimension of graphs
• Computing the metric dimension for chain graphs

zbMATH Keywords

metric dimensionrooted product graphsmetric basiscorona product graphsprimary subgraphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• On the corona of two graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability and the upper dimension of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Notions of metric dimension of corona products: combinatorial and computational results
• The hierarchical product of graphs
• On the Complexity of Metric Dimension
• Title not available (Why is that?)
• A new graph product and its spectrum
• On the metric dimension of corona product of graphs
• Title not available (Why is that?)
• On Metric Generators of Graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs
• On the metric dimension of corona product graphs
• The metric dimension of strong product graphs
• Computing the metric dimension for chain graphs
• Title not available (Why is that?)
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
• On the metric dimension and fractional metric dimension of the hierarchical product of graphs
• The terminal Hosoya polynomial of some families of composite graphs
• Metric dimension parameterized by max leaf number
• Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs
• Computing the Hosoya polynomial of graphs from primary subgraphs

Cited In (16)

• Resolvability and convexity properties in the Sierpiński product of graphs
• Universal lines in graphs
• Metric properties of generalized Sierpiński graphs over stars
• The \(k\)-metric dimension of corona product graphs
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• On vertices contained in all or in no metric basis
• Computing the \(k\)-metric dimension of graphs
• Computing a metric basis of a 2-connected bipartite distance-hereditary graph
• Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs
• Metric dimension of graph join two paths \(P_2\) and \(P_t\)
• On metric dimension of plane graphs with \(\frac{m}{2}\) number of 10 sided faces
• The metric dimension of strong product graphs
• On metric dimension of some planar graphs with \(2n\) odd sided faces
• Computing the metric dimension for chain graphs
• On the mutual visibility in Cartesian products and triangle-free graphs
• Computing vertex resolvability of some regular planar graphs

This page was built for publication: Computing the metric dimension of a graph from primary subgraphs

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