Metric dimension of maximal outerplanar graphs (Q2045286)

The notion of resolving sets and the metric dimension of general graphs were introduced by \textit{P. J. Slater} [in: Proceedings of the 6th southeastern conference on combinatorics, graph theory, and computing. Florida Atlantic University, Boca Raton, 1975. Winnipeg: Utilitas Mathematica Publishing Inc. 549--559 (1975; Zbl 0316.05102)] and \textit{F. Harary} and \textit{R. A. Melter} [Ars Comb. 2, 191--195 (1976; Zbl 0349.05118)], independently. The metric dimension \(\beta(G)\) of a graph \(G(V,E)\) here is the smallest integer \(k\) so that there exists a \(k\)-subset \(S\) of \(V\), say \(S=\{s_1,s_2, \dots,s_k\}\), which gives that all representations of all vertices in \(G\) are distinct. The representation of a vertex \(x\) of \(G\) with respect to \(S\) is defined as the coordinate \(r(x|S)=(d(x,s_1),d(x,s_2), \dots, d(x,s_t))\), where \(d(x,y)\) is the distance between vertices \(x\) and \(y\) in \(G\). Since then, computing the metric dimension of a graph has been widely studied. This paper is concerned with finding the metric dimension of a particular class of graphs, namely outerplanar graphs. Recall that a graph \(G\) is outerplanar if it can be drawn in the plane with no crossing edges and with all the vertices belonging to the outer face of \(G\). Moreover, such a graph \(G\) is said to be maximal if the addition of any edge produces a non-outerplanar graph. The authors derive the bound of \(\beta(G)\) for any maximal outerplanar graph \(G\), namely \(2 \leq \beta(G) \leq \lceil \frac{2n}{5} \rceil\). Such bounds are shown tight. Moreover, all maximal outerplanar graphs with metric dimension 2 have been characterized. A linear algorithm is also established to decide whether the metric dimension of a maximal outerplanar graph is 2. This paper also gives a family of maximal outerplanar graphs of order \(n\) having the metric dimension \(\lceil \frac{2n}{5} \rceil\).