Metric dimension of maximal outerplanar graphs
Mercè Claverol Aguas, Carmen Hernando, Montserrat Maureso, Mercè Ferrater Mora, Hernández Peñalver, Gregorio, Garcia Olaverri, Alfredo Martin, Javier Tejel · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2019
In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if ß(G) denotes the metric dimension of a maximal outerplanar graph G of order n, we prove that 2=ß(G)=¿2n5¿ 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 S of size ¿2n5¿ for G. Moreover, we characterize all maximal outerplanar graphs with metric dimension 2.