Preprint
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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Metric-locating-dominating sets of graphs for constructing related subsets of verticesApplied Mathematics and Computation, 2018
- Computing the k -metric dimension of graphsApplied Mathematics and Computation, 2017
- Identification, location–domination and metric dimension on interval and permutation graphs. I. BoundsTheoretical Computer Science, 2017
- Complexity of metric dimension on planar graphsJournal of Computer and System Sciences, 2017
- Computing the metric dimension for chain graphsInformation Processing Letters, 2015
- The difference between the metric dimension and the determining number of a graphApplied Mathematics and Computation, 2014
- On the metric dimension of circulant and Harary graphsApplied Mathematics and Computation, 2014
- The (Weighted) Metric Dimension of Graphs: Hard and Easy CasesAlgorithmica, 2014
- On the metric dimension of infinite graphsDiscrete Applied Mathematics, 2012
- Landmarks in graphsDiscrete Applied Mathematics, 1996