Metric dimension of maximal outerplanar graphs

DOI10.1007/S40840-020-01068-6MaRDI QIDQ2045286zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1903.11933, http://hdl.handle.net/2117/133862

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (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 1895692 (Why is no real title available?)
• A characterization of some graphs with metric dimension two
• A linear algorithm for embedding planar graphs using PQ-trees
• A linear-time algorithm for drawing a planar graph on a grid
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• Complexity of metric dimension on planar graphs
• Computing the \(k\)-metric dimension of graphs
• Computing the metric dimension for chain graphs
• Computing the metric dimension of wheel related graphs
• Extremal graph theory for metric dimension and diameter
• Graphs with metric dimension two - a characterization
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Landmarks in graphs
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• On the Metric Dimension of Cartesian Products of Graphs
• On the metric dimension of circulant and Harary graphs
• On the metric dimension of infinite graphs
• On unicyclic graphs of metric dimension 2
• Resolvability in graphs and the metric dimension of a graph
• Resolving dominating partitions in graphs
• Resolving sets and semi-resolving sets in finite projective planes
• The (weighted) metric dimension of graphs: hard and easy cases
• The difference between the metric dimension and the determining number of a graph

Cited in

(11)

• The equidistant dimension of graphs
• Resolving sets for higher dimensional projective spaces
• Resolving vertices of graphs with differences
• 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 of metric dimension on planar graphs
• Complexity and equivalency of multiset dimension and ID-colorings
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• scientific article; zbMATH DE number 1560507 (Why is no real title available?)
• 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)