Bounds on metric dimension for families of planar graphs

Abstract

The concept of metric dimension has applications in a variety of fields, such as chemistry, robotic navigation, and combinatorial optimization. We show bounds for graphs with $n$ vertices and metric dimension ${\hat{I}}^2$. For Hamiltonian outerplanar graphs, we have ${\hat{I}}^2\le \lceil \frac{n}{2}\rceil$; for outerplanar graphs in general, we have ${\hat{I}}^2\le \lfloor \frac{2n}{3}\rfloor$; for maximal planar graphs, we have ${\hat{I}}^2\le \lfloor \frac{3n}{4}\rfloor$. We also show that bipyramids have a metric dimension of $\lfloor \frac{2n}{5}\rfloor +1$. It is conjectured that the metric dimension of maximal planar graphs in general is on the order of $\lfloor \frac{2n}{5}\rfloor$.

6 pages. Comments welcomed