On accurate domination in graphs

Abstract

A dominating set of a graph $G$ is a subset $D\subseteq V_G$ 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$. The accurate domination number of $G$, denoted by ${\gamma }_{\mathrm{a}}(G)$, is the cardinality of a smallest set $D$ that is a dominating set of $G$ and no $|D|$-element subset of $V_G\setminus D$ is a dominating set of $G$. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees $G$ for which ${\gamma }_{\mathrm{a}}(G)=\gamma (G)$ are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

12 pages, 1 figure