On the number of fair dominating sets of 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 $\gamma (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$.In this paper, after presenting preliminaries, we count the number of fair dominating sets of some specific graphs.

12 pages, 2 figures