Metric dimension of maximal outerplanar graphs

Mercè Claverol, Alfredo García, Greogorio Hernández, Carmen Hernando, Montserrat Maureso, Mercè Mora, Javier Tejel

Published 2019-03-28Version 1

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.