Global restrained Roman domination in graphs

Document Type : Original paper

Authors

1 Department of Mathematics, Islamic Azad University, Nazarabad Branch, Nazarabad, Alborz, Iran

2 Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

Abstract

A global restrained Roman dominating function on a graph G=(V,E) to be a function f:V→{0,1,2} such that f is a restrained Roman dominating function of both G and its complement G―. The weight of a global restrained Roman dominating function is the value w(f)=Σu∈Vf(u). The minimum weight of a global restrained Roman dominating function of G is called the global restrained Roman domination number of G and denoted by γgrR(G). In this paper we initiate the study of global restrained Roman domination number of graphs. We then prove that the problem of computing γgrR is NP-hard even for bipartite and chordal graphs. The global restrained Roman domination of a given graph is studied versus to the other well known domination parameters such as restrained Roman domination number γrR and global domination number γg by bounding γgrR from below and above involving γrR and γg for general graphs, respectively. We characterize graphs G for which γgrR(G)∈{1,2,3,4,5}. It is shown that: for trees T of order n, γgrR(T)=n if and only if diameter of T is at most 5. Finally, the triangle free graphs G for which γgrR(G)=|V| are characterized.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar and S.R. Mirmehdipour, Bounds on the restrained Roman domination number of a graph, Commun. Comb. Optim. 1 (2016), no. 1, 75–82.  https://doi.org/10.22049/cco.2016.13556
[2] M. Alishahi and D.A. Mojdeh, Global outer connected domination number of a graph, Algebra Discrete Math. 25 (2018), no. 1, 18–26.
[3] J. Amjadi, B. Samadi, and L. Volkmann, Total restrained Roman domination, Commun. Comb. Optim. 8 (2023), no. 3, 575–587.  https://doi.org/10.22049/cco.2022.27628.1303
[4] G. Chartrand and L. Lesniak, Graphs and Digraphs, 4th ed., CRC press, Boca Raton, 2010.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, pp. 365–409.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.  https://doi.org/10.1016/j.akcej.2019.12.001
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, p. 273–307.
[8] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.  https://doi.org/10.1016/j.disc.2003.06.004
[9] P. Dankelmann, J.H. Hattingh, M.A. Henning, and H.C. Swart, Trees with equal domination and restrained domination numbers, J. Global Optim. 34 (2006), 597–607.  https://doi.org/10.1007/s10898-005-8565-z
[10] D. Delić and C. Wang, The global connected domination in graphs, Ars Combin. 114 (2014), 105–110.
[11] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999), no. 1-3, 61–69.  https://doi.org/10.1016/S0012-365X(99)00016-3
[12] G.S. Domke, J.H. Hattingh, and M.A. Henning, Restrained domination in graphs with minimum degree two, 35 (2000), 239–254.
[13] G.S. Domke, J.H. Hattingh, M.A. Henning, and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000), no. 1-3, 1–9.  https://doi.org/10.1016/S0012-365X(99)00036-9
[14] X. Fu, Y. Yang, and B. Jiang, Roman domination in regular graphs, Discrete Math. 309 (2009), no. 6, 1528–1537.  https://doi.org/10.1016/j.disc.2008.03.006
[15] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs (1st ed.), CRC press, 1998.
[16] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 101–115.  https://doi.org/10.1016/S0012-365X(03)00040-2
[17] N. Jafari Rad and L. Volkmann, Roman domination perfect graphs, An. St. Univ. Ovidius Constanta, Ser. Mat. 19 (2011), no. 3, 167–174.
[18] R. Kala and T.R.N. Vasantha, Global Restrained Domination Number of a Graph, pp. 39–49, Narosa Publishing House Pvt. Limited, New Dehli, 2009.
[19] V.R. Kulli and B. Janakiram, The total global domination number of a graph, Indian J. Pure Appl. Math. 27 (1996), no. 6, 537–542.
[20] C.H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619. https://doi.org/10.1007/s10878-012-9482-y
[21] A.C. Martinez, A. Martinez Arias, and M.M. Castillo, A characterization relating domination, semitotal domination and total Roman domination in trees, Commun. Comb. Optim. 6 (2021), no. 2, 197–209.  https://doi.org/10.22049/cco.2020.26892.1157
[22] D.A. Mojdeh and M. Alishahi, Outer independent global dominating set of trees and unicyclic graphs, Electron. J. Graph Theory Appl. 7 (2019), no. 1, 121–145.  https://doi.org/10.5614/ejgta.2019.7.1.10
[23] D.A. Mojdeh, G. Hao, I. Masoumi, and A. Parsian, Unique response strong Roman dominating functions of graphs, Electron. J. Graph Theory Appl. 9 (2021), no. 2, 469–484.  https://dx.doi.org/10.5614/ejgta.2021.9.2.18
[24] P.R.L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4 (2015), no. 1, 1–17.  https://doi.org/10.22108/toc.2015.4395
[25] P.R.L. Pushpam and S. Padmapriea, Global Roman domination in graphs, Discrete Appl. Math. 200 (2016), 176–185.  https://doi.org/10.1016/j.dam.2015.07.014
[26] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[27] D.S. Vladimir, Roman domination excellent graphs: trees, Commun. Comb. Optim. 3 (2018), no. 1, 1–24.   https://doi.org/10.22049/cco.2017.25806.1041
Communications in Combinatorics and Optimization
Volume 10, Issue 2
June 2025
Pages 295-317

Files

Share

How to cite

Statistics