An improved upper bound for the fair domination number of maximal outerplanar graphs

@misc{caro2026improved,
  title = {{An improved upper bound for the fair domination number of maximal outerplanar graphs}},
  author = {Yair Caro and Riste Škrekovski},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23076},
  eprint = {2609.23076},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23076},
}

TY  - UNPB
TI  - An improved upper bound for the fair domination number of maximal outerplanar graphs
AU  - Yair Caro
AU  - Riste Škrekovski
PY  - 2026
DA  - 2026/09/19
PB  - arXiv
DO  - 10.48550/arxiv.2609.23076
UR  - https://arxiv.org/abs/2609.23076
AB  - A dominating set D of a graph G is a \emph{fair dominating set} if every two vertices outside D have the same number of neighbors in D, and the \emph{fair domination number} fd(G) is the minimum cardinality of such a set. Caro, Hansberg and Henning, who introduced this parameter, proved that fd(G)<17n/19 for every maximal outerplanar graph G of order n≥3, and asked whether this bound is asymptotically best possible. We show that it is not the case by proving fd(G)≤(7n−3)/8<7n/8 for every maximal outerplanar graph G of order n≥3, and we exhibit an infinite family of maximal outerplanar graphs with fd(G)/n→7/9, so that the best asymptotic constant lies between 7/9 and 7/8.
ER  -