سامانه مدیریت نشریات علمی دانشگاه صنعتی شاهرود

Mirhoseini, S.H., Jafari Rad, N.. (1401). ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION. , 10(2), 189-202. doi: 10.22044/jas.2021.11146.1554
S.H. Mirhoseini; N. Jafari Rad. "ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION". , 10, 2, 1401, 189-202. doi: 10.22044/jas.2021.11146.1554
Mirhoseini, S.H., Jafari Rad, N.. (1401). 'ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION', , 10(2), pp. 189-202. doi: 10.22044/jas.2021.11146.1554
Mirhoseini, S.H., Jafari Rad, N.. ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION. , 1401; 10(2): 189-202. doi: 10.22044/jas.2021.11146.1554

ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION

Journal of Algebraic Systems
دوره 10، شماره 2، فروردین 2023، صفحه 189-202    اصل مقاله (420.35 K)
نوع مقاله: Original Manuscript
شناسه دیجیتال (DOI): 10.22044/jas.2021.11146.1554
نویسندگان
S.H. Mirhoseini؛ N. Jafari Rad*
Department of Mathematics, Shahed University, Tehran, Iran.
چکیده
‎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‎.
کلیدواژه‌ها
Dominating set‎؛ ‎perfect dominating set‎؛ ‎Roman dominating function‎؛ ‎perfect Roman dominating function‎؛ ‎APX-hard
مراجع
  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.

آمار
تعداد مشاهده مقاله: 759
تعداد دریافت فایل اصل مقاله: 532