ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION

Document Type : Original Manuscript

Authors

Department of Mathematics, Shahed University, Tehran, Iran.

Abstract

‎A perfect Roman dominating function (PRDF) on a graph $G$ is a function $ f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to exactly one vertex $v$ for which $f(v) = 2$‎. ‎The weight of a PRDF $f$ is the sum of the weights of the vertices under $f$‎. ‎The perfect Roman domination number of $G$ is the minimum weight of a PRDF in $G$‎. ‎In this paper we study algorithmic and computational complexity aspects of the minimum perfect Roman domination problem (MPRDP)‎. ‎We first correct the proof of a result published in [Bulletin‎
‎Iran‎. ‎Math‎. ‎Soc‎. ‎14(2020)‎, ‎342--351]‎, ‎and using a similar argument‎, ‎show that MPRDP is APX-hard for graphs with bounded degree 4‎.
‎We prove that the decision problem associated to MPRDP is NP-complete even when restricted to star convex bipartite graphs‎. ‎Moreover‎, ‎we show that MPRDP is solvable in linear time for bounded tree-width‎
‎graphs‎. ‎We also show that the perfect domination problem and perfect Roman domination problem are not equivalent in computational complexity aspects‎. ‎Finally we propose an integer linear programming formulation for MPRDP‎.

Keywords

References

  1. H. Abdollahzadeh Ahangar, A. Bahramandpour, S. M. Sheikholeslami, N. D. Soner, Z. Tahmasbzadehbaee and L. Volkmann, Maximal Roman domination numbers in graphs, Utilitas Math., 103 (2017), 245–258.
    2. H. Abdollahzadeh Ahangar, M. Chellali, D. Kuziak and V. Samodivkin, On maximal Roman domination in graphs, Int. J. Comput. Math., 93(7) (2016), 1093–1102.
    3. H. Abdollahzadeh Ahangar, L. Shahbazi, R. Khoeilar, and S.M. Sheikholeslami, Bounds on signed total double Roman domination, Commun. Comb. Optim., 5 (2020), 191–206.
    4. S. Banerjee, J. Mark Keil and D. Pradhan, Perfect Roman domination in graphs, Theoretical Comput. Sci., 796 (2019), 1–21.
    5. P. Chakradhar and P. Venkata Subba Reddy, Complexity aspects of variants of independent roman domination in graphs, Bull. Iran. Math. Soc., 14 (2020),
    342–351.
    6. M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, (2020) Roman Domination in Graphs. In: Haynes T.W., Hedetniemi S.T., Henning M.A. (eds) Topics in Domination in Graphs, Developments in Mathematics, vol 64. Springer, Cham. https://doi.org/10.1007/978-3-030-51117-3-11.
    7. M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, In: Structures of Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, to appear 2020.
    8. M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE J. Graphs Combin., 17 (2020), 966–984.
    9. M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Comb.
    Comput. (to appear).
    10. C. Chen and M. Lin, Counting independent sets in tree convex bipartite graphs, Discr. Appl. Math., 218 (2017), 113–122.
    11. J. Chlebikova and M. Chlebik, The complexity of combinatorial optimization problems on d-dimensional boxes, SIAM J. Discrete Math., 21 (2007), 158–169.
    12. E. J. Cockayane, P. M. Dreyer Jr., S. M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, Discrete Math., 278 (2004), 11–22.
    13. B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. and Comput., 85 (1990), 12–75.
    14. M. R. Garey, D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-completeness, Freeman, New York, 1979.
    15. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
    16. M. A. Henning and W. F. Klostermeyer, Perfect Roman domination in regular graphs, Appl. Anal. Discrete Math., 12 (2018), 143–152.
    17. M. A. Henning, W. F. Klostermeyer, and G. MacGillivray, Perfect Roman domination in trees, Discrete Appl. Math., 236 (2018), 235–245.
    18. W. Klostermeyer, A taxonomy of perfect domination, J. Discrete Math. Sci. Cryptography, 18 (2015), 105–116.
    19. A. Pandey and M. A. Henning, Algorithmic aspects of semitotal domination in graphs, Theo. Comput. Sci., 766 (2019), 46–57.

20. A. Pandey and B. S. Panda, Algorithm and Hardness Result for Outerconnected dominating set in graphs. J. Graph Algorithms Appl., 18 (2014),
493–518.
21. A. Pandey, S. Paul and B. S. Panda, Algorithmic aspects of b-disjunctive domination in graphs, J. Comb. Optim., 36 (2018), 572–590.

Journal of Algebraic Systems
Volume 10, Issue 2
January 2023
Pages 189-202

Files

Share

How to cite

Statistics