Algorithmic aspects of certified domination in graphs

Document Type : Original paper

Authors

1 IcfaiTech (Faculty of Science & Technology) ICFAI Foundation for Higher Education, Hyderabad, India

2 Director (n-CARDMATH) Kalasalingam University Anand Nagar, Krishnankoil-626 126 Tamil Nadu, India

3 Department of Computer Science and Engineering, National Institute of Technology Warangal, Telangana, India

4 National Institute of Technology Warangal

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 7, Issue 2
December 2022
Pages 247-255

Files

Share

How to cite

Statistics