Enumeration of accurate dominating sets

Saeid Alikhani, Maryam Safazadeh, Nima Ghanbari

Published 2021-01-22Version 1

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$. A dominating set $D$ is an accurate dominating set of $G$, if no $|D|$-element subset of $V\setminus D$ is a dominating set of $G$. The accurate domination number, $\gamma_a(G)$, is the cardinality of a smallest accurate dominating set $D$. In this paper, after presenting preliminaries, we count the number of accurate dominating sets of some specific graphs.