On Certified Perfect Domination in Graphs

Abstract

Let \( G = (V(G),E(G)) \) be a simple graph. A perfect dominating set \( J \subseteq V(G) \) is called a \emph{certified perfect dominating set} of \( G \) if each vertex \( a \in J \) has either no neighbors or at least two neighbors in \( V(G) \setminus J \). The \emph{certified perfect domination number} of \( G \) \( \gamma_{cerp}(G) \) represents the smallest size of a certified perfect dominating set in \( G \). A certified perfect dominating set  of \( G \) that attains this minimum size, i.e., $|J|=\gamma_{cep}(G)$ is referred to as a \( \gamma_{cerp} \)-set. In this paper, we first present some upper bounds for the certified perfect domination number of \( G \), investigate the relationship between certified domination and certified perfect domination parameters, and determine graphs with small and large values of these parameters. Secondly, we characterize the graphs with \( \gamma_{cerp}(G) = n \) and \( \gamma_{cerp}(G) = \gamma_{cer}(G) \). Lastly, we characterize the certified perfect dominating set under the lexicographic and Cartesian products of two graphs, determine its certified perfect domination number, and identify a non-\(\gamma_{cerp}\)-graph under these binary operations.