|
|
|
|
Algorithmic Aspects of Certified Domination in Graphs
|
|
|
|
|
|
|
|
نویسنده
|
Kumar Jakkepalli Pavan ,Arumugam Subramanian ,Khandelwal Himanshu ,Reddy P. Venkata Subba
|
|
منبع
|
Communications In Combinatorics And Optimization - 2022 - دوره : 7 - شماره : 2 - صفحه:247 -255
|
|
|
|
|
چکیده
|
A dominating set d of a graph g=(v,e) is called a certified dominating set of g if |n(v)∩(v∖d)| is either 0 or at least 2 for all v∈d. the certified domination number γcer(g) is the minimum cardinality of a certified dominating set of g. in this paper, we prove that the decision problem corresponding to γ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.
|
|
کلیدواژه
|
Certified Domination ,Np-Complete ,Tree-Convex Bipartite Graphs
|
|
آدرس
|
Icfai Foundation For Higher Education, Icfaitech (Faculty Of Science & Technology), India, Kalasalingam Academy Of Research And Education, India, National Institute Of Technology, Department Of Computer Science And Engineering, India, National Institute Of Technology, Department Of Computer Science And Engineering, India
|
|
پست الکترونیکی
|
pvsr@nitw.ac.in
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|