Fair coalition in graphs

Abstract

Let $G=(V,E)$ be a simple graph. A dominating set of $G$ is a subset $D\subseteq V$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$. The cardinality of a smallest dominating set of $G$, denoted by ${\hat{I}}^3(G)$, is the domination number of $G$. For $k\ge 1$, a $k$-fair dominating set ($kFD$-set) in $G$, is a dominating set $S$ such that $|N(v)\cap D|=k$ for every vertex $v\in V\setminus D$. A fair dominating set in $G$ is a $kFD$-set for some integer $k\ge 1$. We consider $1FD$-sets and define a fair coalition in a graph $G$ as a pair of disjoint subsets $A_1,A_2\subseteq A$ that satisfy the following conditions: (a) neither $A_1$ nor $A_2$ constitutes a $1$-fair dominating set of $G$, and (b) $A_1\cup A_2$ constitutes a $1$-fair dominating set of $G$. A fair coalition partition of a graph $G$ is a partition $\hat{I}\yen =\{A_1,A_2,\dots ,A_k\}$ of its vertex set such that every set $A_i$ of $\hat{I}\yen$ is either a singleton $1$-fair dominating set of $G$, or is not a $1$-fair dominating set of $G$ but forms a fair coalition with another non-$1$-fair dominating set $A_j\in \hat{I}\yen$. We define the fair coalition number of $G$ as the maximum cardinality of a fair coalition partition of $G$, and we denote it by ${\mathcal{C}}_f(G)$. We initiate the study of the fair coalition in graphs and obtain ${\mathcal{C}}_f(G)$ for some specific graphs.

17 pages, 3 figures