Document Type : Research Paper

Authors

• Saeid Alikhani ¹
• Davood Bakhshesh ²
• Nasrin Jafari ³
• Maryam Safazadeh ³

¹ Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

² Department of Computer Science, University of Bojnord, Bojnord, Iran.

³ Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran.

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 the smallest dominating set of $G$, denoted by $\gamma(G)$, is the domination number of $G$. For $k \geq 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\geq 1$. Let ${\cal D}_f(G,i)$ be the family of the
fair dominating sets of a graph $G$ with cardinality $i$ and let
$d_f(G,i)=|{\cal D}_f(G,i)|$.
The fair domination polynomial of $G$ is $D_f(G,x)=\sum_{ i=1}^{|V(G)|} d_f(G,i) x^{i}$. In this paper, 
after computation of the fair domination number of power of cycle, we count the number of the fair dominating sets of certain graphs such as cubic graphs of order~$10$, power of paths, and power of cycles. As a consequence, all cubic graphs of order $10$ and especially the Petersen graph are determined uniquely by their fair domination polynomial. 

Keywords

• fair dominating set
• Petersen graph
• power of path and cycle
• unimodal