Connected Certified Domination in Graphs: Properties and Algorithmic Aspects
A certified dominating set \(D\) of a graph \(Γ=(V_Γ,E_Γ)\) denoted by \(γ_cer \)-set, is the subset of \(V_Γ\) such that \(|N(u)(V_Γ-D)|\) is either \(0\) or \(2\), \(\) \(uD\). A set \(D_cV_Γ\) is called a connected certified dominating set \((γ_cer ^c\)-set\()\) if \(D_c\) is \(γ_cer \)-set and \(Γ[D_c]\) is connected. Also, if \(D_c\) has no proper subset, then it is a smallest \(γ_cer ^c\)-set, and the cardinality of the smallest \(γ_cer ^c\)-set is called as connected certified domination number (CCDN) of the graph \(Γ\) represented by \(γ_cer ^c(Γ)\). 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. , number=2, journal=Communications in Mathematics and Applications, author=Ilyass, Azham and Mani, Naveen, year=2024, month=Nov., pages=817–827