Metric dimension of maximal outerplanar graphs

DOI10.1007/S40840-020-01068-6zbMATH Open1478.05038arXiv1903.11933OpenAlexW3127933750MaRDI QIDQ2045286FDOQ2045286

Authors: Mercè Claverol, Gregorio Hernández, C. Hernando, Mercè Mora, Alfredo García, Montserrat Maureso, Javier Tejel 

Publication date: 12 August 2021

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Abstract: In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $$ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of $G$ is 2 and to build a resolving set of size $lceilfrac2n5ceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2.

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

Recommendations

• Complexity of metric dimension on planar graphs
• On the Complexity of Metric Dimension
• Resolvability in graphs and the metric dimension of a graph
• The metric dimension and metric independence of a graph
• Extremal graph theory for metric dimension and diameter

zbMATH Keywords

metric dimensionresolving setmaximal outerplanar graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Cites Work

• A linear algorithm for embedding planar graphs using PQ-trees
• Resolvability in graphs and the metric dimension of a graph
• Resolving sets and semi-resolving sets in finite projective planes
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Landmarks in graphs
• Computing the metric dimension of wheel related graphs
• Title not available (Why is that?)
• Graphs with metric dimension two - a characterization
• A characterization of some graphs with metric dimension two
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• A linear-time algorithm for drawing a planar graph on a grid
• Extremal graph theory for metric dimension and diameter
• On the metric dimension of circulant and Harary graphs
• The difference between the metric dimension and the determining number of a graph
• Computing the \(k\)-metric dimension of graphs
• Computing the metric dimension for chain graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Complexity of metric dimension on planar graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• On the metric dimension of infinite graphs
• Title not available (Why is that?)
• Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Title not available (Why is that?)
• Resolving dominating partitions in graphs
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• Title not available (Why is that?)

Cited In (11)

• The equidistant dimension of graphs
• Resolving vertices of graphs with differences
• Resolving sets for higher dimensional projective spaces
• Resolvability and convexity properties in the Sierpiński product of graphs
• Outerplanar graphs having the metric extension property. II
• On the metric representation of the vertices of a graph
• Complexity and equivalency of multiset dimension and ID-colorings
• Complexity of metric dimension on planar graphs
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Title not available (Why is that?)
• Further contributions on the outer multiset dimension of graphs

This page was built for publication: Metric dimension of maximal outerplanar graphs

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