Fair domination in graphs (Q449132)

In this paper the authors prove many results about the fair domination number, \(\text{fd}(G)\), of a graph, \(G\). The first main theorem shows that a graph, \(G\) with \(n\geq3\) vertices, none of which are isolated, has \(\text{fd}(G)\leq n-2\) and this bound is sharp. Specializing to trees with \(n\geq2\) vertices, the authors prove that \(\text{fd}(T) \leq n/2\) with equality exactly when the tree is the corona of a tree. Further, they give two conditions equivalent to a tree with \(n\geq 3\) vertices and \(\ell\) leaves having \(\text{fd}(T) < n -\ell\). Another family of graphs that the authors consider are the maximal outerplanar graphs, which are graphs that are triangulations of polygons. They prove that for a maximal outerplanar graph with \(n\geq 3\) vertices, \(\text{fd}(G) < 17n/19\). The final result of the paper gives an inequality for the fair domination number of a disjoint union of graphs. The paper concludes with five open problems about fair domination number. There are a number of other smaller results that are not described here.