Graphs with equal domination and certified domination numbers

Abstract

A set $D$ of vertices of a graph $G=(V_{G},E_{G})$ is a dominating set of $G$ if every vertex in $V_{G}-D$ is adjacent to at least one vertex in $D$. The domination number (upper domination number, respectively) of $G$, denoted by $\gamma(G)$ ($\Gamma(G)$, respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of $G$. A subset $D\subseteq V_G$ is called a certified dominating set of $G$ if $D$ is a dominating set of $G$ and every vertex in $D$ has either zero or at least two neighbors in $V_{G}-D$. The cardinality of a smallest (largest minimal, respectively) certified dominating set of $G$ is called the certified (upper certified, respectively) domination number of $G$ and is denoted by $\gamma_{\rm cer}(G)$ ($\Gamma_{\rm cer}(G)$, respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.