Global restrained Roman domination in graphs

Document Type : Original paper

Authors

1 Department of Mathematics, Islamic Azad University,

2 Departtment of Mathematics, University of Mazandaran

Abstract

A global restrained Roman dominating function on a graph $G=(V,E)$ to be a function $f:V\rightarrow\{0,1,2\}$ such that $f$ is a restrained Roman dominating function of both $G$ and its complement $\overline G$. The weight of a global restrained Roman dominating function is the value $w(f)=\Sigma_{u \in V} f(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 $\gamma_{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 $\gamma_{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 $\gamma_{rR}$ and global domination number $\gamma_g$ by bounding $\gamma_{grR}$ from below and above involving $\gamma_{rR}$ and $\gamma_g$ for general graphs, respectively. We characterize graphs $G$ for which $\gamma_{grR}(G)\in \{1,2,3,4,5\}$. It is shown that: for trees $T$ of order $n$, $\gamma_{grR}(T)=n$ if and only if diameter of $T$ is at most $5$. Finally, the triangle free graphs $G$ for which $\gamma_{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.
https://doi.org/10.1007/978-3-030-51117-3 11
[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´c 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

Articles in Press, Accepted Manuscript
Available Online from 13 November 2023

Files

Share

How to cite

Statistics