Enumeration of accurate dominating sets

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$. 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.

13 pages, 6 figures