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

Abstract

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} $\mathrm{fd}(G)$ is the minimum cardinality of such a set. Caro, Hansberg and Henning, who introduced this parameter, proved that $\mathrm{fd}(G)<17n/19$ for every maximal outerplanar graph $G$ of order $n\ge 3$, and asked whether this bound is asymptotically best possible. We show that it is not the case by proving $\mathrm{fd}(G)\le (7n-3)/8<7n/8$ for every maximal outerplanar graph $G$ of order $n\ge 3$, and we exhibit an infinite family of maximal outerplanar graphs with $\mathrm{fd}(G)/n\to 7/9$, so that the best asymptotic constant lies between $7/9$ and $7/8$.

16 pages, 1 figure