Some new results on the number of fair dominating sets

Document Type : Research Paper

Authors

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

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

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

10.22059/jac.2022.90381

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

Journal of Algorithms and Computation
Volume 54, Issue 2
December 2022
Pages 1-12

Files

Share

How to cite

Statistics