Connected Certified Domination in Graphs: Properties and Algorithmic Aspects
Azham Ilyass, Naveen Kumar Mani · Communications in Mathematics and Applications · 2024
A certified dominating set \(D\) of a graph \(\Gamma=(V_\Gamma,E_\Gamma)\) denoted by \(\gamma_{\mathit{cer}}\)-set, is the subset of \(V_\Gamma\) such that \(|N(u)\cap(V_\Gamma-D)|\) is either \(0\) or \(2\), \(\forall\) \(u\in D\). A set \(\mathcal{D}_c\subseteq V_\Gamma\) is called a connected certified dominating set \((\gamma_{\mathit{cer}}^c\)-set\()\) if \(\mathcal{D}_c\) is \(\gamma_{\mathit{cer}}\)-set and \(\Gamma[\mathcal{D}_c]\) is connected. Also, if \(\mathcal{D}_c\) has no proper subset, then it is a smallest \(\gamma_{\mathit{cer}}^c\)-set, and the cardinality of the smallest \(\gamma_{\mathit{cer}}^c\)-set is called as connected certified domination number (CCDN) of the graph \(\Gamma\) represented by \(\gamma_{\mathit{cer}}^c(\Gamma)\). In this article, we continue the study of connected certified domination. Herein, we classify graphs with larger values of CCDN and then we will study some properties of connected certified domination. Moreover, we will provide upper bounds and Nordhaus-Gaddum results for the CCDN. Additionally, we will prove that the connected certified domination problem is NP-complete for star convex bipartite graphs, comb convex bipartite graphs, and planar graphs.