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.

Keywords

• domination
• certified domination