On the fault-tolerant metric dimension of maximal outerplanar graphs

@misc{hernando2026faulttolerant,
  title = {{On the fault-tolerant metric dimension of maximal outerplanar graphs}},
  author = {Carmen Hernando and Montserrat Maureso and Mercè Mora and Javier Tejel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.13374},
  eprint = {2610.13374},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.13374},
}

TY  - UNPB
TI  - On the fault-tolerant metric dimension of maximal outerplanar graphs
AU  - Carmen Hernando
AU  - Montserrat Maureso
AU  - Mercè Mora
AU  - Javier Tejel
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.13374
UR  - https://arxiv.org/abs/2610.13374
AB  - Given a graph G, a set W of vertices of G is a resolving set if, for any pair of vertices z_1 and z_2 of G, there is a vertex w∈ W such that d(w,z_1)≠ d(w,z_2), where d(u,v) denotes the length of a shortest path between the vertices u and v. The metric dimension of a graph G, β(G), is the minimum cardinality of a resolving set of G. A resolving set W is fault-tolerant if W∖ {w} is a resolving set for any w∈ W. The fault-tolerant metric dimension of a graph G, denoted by β'(G), is the minimum cardinality of a fault-tolerant resolving set of G. In this paper, we study the fault-tolerant metric dimension problem in maximal outerplanar graphs. In particular, we show that there are exactly two maximal outerplanar graphs with β'(G)=3. We also show that 4≤ β'(G) ≤ 6 for any maximal outerplanar graph G of order at least 7 and metric dimension 2. Moreover, we establish the upper bound β'(G) ≤ ⌈ 2n/3 ⌉ for maximal outerplanar graphs G of order n≥ 5, by building in linear time a fault-tolerant resolving set of cardinality ⌈ 2n/3 ⌉.
ER  -