$k$-Fair Coalitions in Graphs

Abstract

Let $G=(V,E)$ be a simple graph. A subset $S\subseteq V$ is called a $k$-fair dominating set if every vertex not in $S$ has exactly $k$ neighbors in $S$. Two disjoint sets $A,B\subseteq V$ form a $k$-fair coalition of $G$ if neither $A$ nor $B$ is a $k$-fair dominating set and the union $A\cup B$ is a $k$-fair dominating set of $G$. A partition $\ddot{I}€=\{V_1,V_2,\dots ,V_m\}$ of $V$ is called a $k$-fair coalition partition, if every set $V_i\in \ddot{I}€$, either $V_i$ is a $k$-fair dominating set with exactly $k$ vertices, or $V_i$ is not a $k$-fair dominating set, but forms a $k$-fair coalition with some other set $V_j$ in $\ddot{I}€$. The $k$-fair coalition number $C_{kf}(G)$ is the largest possible size of a $k$-fair coalition partition for $G$. The objective of this study is to initiate an examination into the notion of $k$-fair coalitions in graphs and present essential findings.

16 pages