Metric Dimension of Maximal Outerplanar Graphs

Claverol, M. ; García, A. (Universidad de Zaragoza) ; Hernández, G. ; Hernando, C. ; Maureso, M. ; Mora, M. ; Tejel, J. (Universidad de Zaragoza)

Resumen: 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.

Idioma: Inglés

DOI: 10.1007/s40840-020-01068-6

Año: 2021

Publicado en: Bulletin of the Malaysian Mathematical Sciences Society 44 (2021), 2603–2630
ISSN: 0126-6705

Factor impacto JCR: 1.397 (2021)

Categ. JCR: MATHEMATICS rank: 81 / 333 = 0.243 (2021) - Q1 - T1

Factor impacto CITESCORE: 2.4 - Mathematics (Q2)

Factor impacto SCIMAGO: 0.598 - Mathematics (miscellaneous) (Q2)

Financiación: info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT

Tipo y forma: Artículo (PostPrint)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)