TY - JOUR ID - 14269 TI - Algorithmic aspects of certified domination in graphs JO - Communications in Combinatorics and Optimization JA - CCO LA - en SN - 2538-2128 AU - Jakkepalli, Pavan Kumar AU - Arumugam, Subramanian AU - Khandelwal, Himanshu AU - P., Venkata Subba Reddy AD - IcfaiTech (Faculty of Science & Technology) ICFAI Foundation for Higher Education, Hyderabad, India AD - Director (n-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626 126 Tamil Nadu, India AD - Department of Computer Science and Engineering, National Institute of Technology Warangal, Telangana, India AD - National Institute of Technology Warangal Y1 - 2022 PY - 2022 VL - 7 IS - 2 SP - 247 EP - 255 KW - Certified domination KW - NP-complete KW - Tree-convex bipartite graphs DO - 10.22049/cco.2021.27302.1226 N2 - A dominating set $ D $ of a graph $ G=(V,E) $ is called a certified dominating set of $ G $ if $\vert N(v) \cap (V \setminus D)\vert$ is either 0 or at least 2 for all $ v \in D$. The certified domination number $\gamma_{cer}(G) $ is the minimum cardinality of a certified dominating set of $ G $. In this paper, we prove that the decision problem corresponding to $\gamma_{cer}(G) $ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. We also prove that it is linear time solvable for chain graphs, threshold graphs and bounded tree-width graphs. UR - http://comb-opt.azaruniv.ac.ir/article_14269.html L1 - http://comb-opt.azaruniv.ac.ir/article_14269_0dabbd07d38631d59ef285a2fe950400.pdf ER -