آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,540 |
| تعداد مشاهده مقاله | 1,631,203 |
| تعداد دریافت فایل اصل مقاله | 1,528,499 |
Algorithmic aspects of certified domination in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 21، دوره 7، شماره 2، اسفند 2022، صفحه 247-255 اصل مقاله (397.15 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 | ||
| مراجع | ||
|
[1] H. Abdollahzadeh Ahangar, J. Amjadi, N. Jafari Rad, and V. Samodivkin, Total k-rainbow domination numbers in graphs, Commun. Comb. Optim. 3 (2018), no. 1, 37–50.
[2] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[3] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation 85 (1990), no. 1, 12–75.
4] M. Dettlaff, M. Lemańska, J. Topp, R. Ziemann, and P. Zyliński, ˙ Certified domination, AKCE Int. J. Graphs Combin. 17 (2020), no. 1, 86–97.
[5] M.E. Dyer and A.M. Frieze, Planar 3DM is NP-complete, J. Algorithms 7 (1986), no. 2, 174–184.
[6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[7] , Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[8] W. Jiang, T. Liu, T. Ren, and K. Xu, Two hardness results on feedback vertex sets, Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Springer, 2011, pp. 233–243.
[9] R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Springer, 1972, pp. 85–103.
[10] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
[11] J. Pavan Kumar and P. Venkata Subba Reddy, Algorithmic aspects of 2-secure domination in graphs, J. Comb. Optim., (In press).
[12] J. Pavan Kumar, P. Venkata Subba Reddy, and S. Arumugam, Algorithmic complexity of secure connected domination in graphs, AKCE Int. J. Graphs Combin. 17 (2020), no. 3, 1010–1013.
[13] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International Symposium on Algorithms and Computation, Springer, 2004, pp. 871–883.
[14] M. Vikas and P. Venkata Subba Reddy, Algorithmic aspects of quasi-total Roman domination in graphs, Commun. Comb. Optim., (In press).
[15] D.B. West, Introduction to Graph Theory, Prentice hall, Upper Saddle River, 2001. | ||
|
آمار تعداد مشاهده مقاله: 1,206 تعداد دریافت فایل اصل مقاله: 1,721 |
||