Metric dimension of maximal outerplanar graphs

Abstract

In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $\beta (G)$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $2\le \beta (G)\le \lceil \frac{2n}{5}\rceil$ 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 $\lceil \frac{2n}{5}\rceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2.

arXiv comment25 pages, 16 figures

References in corpus (5)

• On the Metric Dimension of Cartesian Products of Graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
• Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• Bounds on metric dimension for families of planar graphs

Cited by in corpus (1)

• Total domination in plane triangulations