آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 77 |
| تعداد مقالات | 707 |
| تعداد مشاهده مقاله | 680,934 |
| تعداد دریافت فایل اصل مقاله | 492,952 |
Algorithmic aspects of certified domination in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 08 مرداد 1400 اصل مقاله (396.65 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27302.1226 | ||
| نویسندگان | ||
Pavan Kumar Jakkepalli   1؛ Subramanian Arumugam2؛ Himanshu Khandelwal3؛ Venkata Subba Reddy P.4
| ||
| 1IcfaiTech (Faculty of Science & Technology) ICFAI Foundation for Higher Education, Hyderabad, India | ||
| 2Director (n-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626 126 Tamil Nadu, India | ||
| 3Department of Computer Science and Engineering, National Institute of Technology Warangal, Telangana, India | ||
| 4National Institute of Technology Warangal | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Certified domination؛ NP-complete؛ Tree-convex bipartite graphs | ||
|
آمار تعداد مشاهده مقاله: 54 تعداد دریافت فایل اصل مقاله: 45 |
||
