On Certified Perfect Domination in Graphs (European Journal of Pure and Applied Mathematics, 2025)
Let \( G = (V(G),E(G)) \) be a simple graph. A perfect dominating set \( J \subseteq V(G) \) is called a 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 certified perfect domination number of \( G \) \( γ_{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|=γ_{cep}(G)$ is referred to as a \( γ_{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 \( γ_{cerp}(G) = n \) and \( γ_{cerp}(G) = γ_{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-\(γ_{cerp}\)-graph under these binary operations.
Keywords: certified domination; perfect domination; certified perfect domination; lexicographic product; Cartesian product