Computing the metric dimension of a graph from primary subgraphs

DOI10.7151/DMGT.1934MaRDI QIDQ503686zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 3482387 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3331438 (Why is no real title available?)
• A new graph product and its spectrum
• Computing the Hosoya polynomial of graphs from primary subgraphs
• Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs
• Computing the metric dimension for chain graphs
• Metric dimension parameterized by max leaf number
• Notions of metric dimension of corona products: combinatorial and computational results
• On Metric Generators of Graphs
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
• On the Complexity of Metric Dimension
• On the Metric Dimension of Cartesian Products of Graphs
• On the corona of two graphs
• On the metric dimension and fractional metric dimension of the hierarchical product of graphs
• On the metric dimension of corona product graphs
• On the metric dimension of corona product of graphs
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• The hierarchical product of graphs
• The metric dimension of strong product graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs
• The terminal Hosoya polynomial of some families of composite graphs

Cited in

(16)

• Computing vertex resolvability of some regular planar graphs
• 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
• Computing the metric dimension for chain graphs
• On metric dimension of some planar graphs with \(2n\) odd sided faces
• On the mutual visibility in Cartesian products and triangle-free 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)