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

Yair Caro; Riste \v{S}krekovski

In the authors' words

A dominating set $D$ of a graph $G$ is a fair dominating set if every two vertices outside $D$ have the same number of neighbors in $D$ , and the fair domination number $f d (G)$ is the minimum cardinality of such a set. Caro, Hansberg and Henning, who introduced this parameter, proved that $f d (G) < 17 n /19$ for every maximal outerplanar graph $G$ of order $n \geq 3$ , and asked whether this bound is asymptotically best possible. We show that it is not the case by proving $f d (G) \leq (7 n - 3) /8 < 7 n /8$ for every maximal outerplanar graph $G$ of order $n \geq 3$ , and we exhibit an infinite family of maximal outerplanar graphs with $f d (G) / n \to 7/9$ , so that the best asymptotic constant lies between $7/9$ and $7/8$ .

Main resultLimitation the authors admit

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

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs