Algorithmic aspects of certified domination in graphs

Communications in Combinatorics and Optimization

article

Jakkepalli, Pavan Kumar¹  Arumugam, Subramanian²  Khandelwal, Himanshu³  P., Venkata Subba Reddy⁴ 

[1] IcfaiTech ,(Faculty of Science &,amp,amp,amp, Technology) ICFAI Foundation for Higher Education;Director ,(n-CARDMATH) Kalasalingam University Anand Nagar;Department of Computer Science and Engineering, National Institute of Technology Warangal;National Institute of Technology Warangal

关键词: Certified domination;    NP-complete;    Tree-convex bipartite graphs.;   

DOI  :  10.22049/cco.2021.27302.1226

学科分类：社会科学、人文和艺术（综合）

来源: Azarbaijan Shahide Madani Universit

【 摘 要 】

A dominating set D of a graph G = (V, E) is called a certified dominatingset of G if |N(v)∩(V \D)| is either 0 or at least 2 for all v ∈ D. The certified dominationnumber γcer(G) is the minimum cardinality of a certified dominating set of G. In thispaper, we prove that the decision problem corresponding to γcer(G) is NP-completefor split graphs, star convex bipartite graphs, comb convex bipartite graphs and planargraphs. We also prove that it is linear time solvable for chain graphs, threshold graphsand bounded tree-width graphs.

【 授权许可】

CC BY-SA