Further Results on Generous Roman Domination

Document Type : Original Scientific Paper

Authors

1 Department of Mathematics,‎ Azarbaijan Shahid Madani University, Tabriz‎, ‎I. R‎. ‎Iran

2 LAMDA-RO Laboratory‎, ‎ ‎Department of Mathematics, University of Blida,‎ B.P‎. ‎270‎, ‎Blida‎, ‎Algeria

Abstract

‎Let G=(V(G),E(G)) be a graph and h be a function defined from V(G) to‎ {0,1,2,3}. A vertex x with h(x)=0 is said to be‎ undefended with respect to $h$ if it has no neighbor assigned‎ 2 or 3 under h‎. ‎The function h is called a‎ generous Roman dominating function (GRD-function) if for every vertex with‎ h(x)=0 there exists at least a vertex y with $h(y)\geq2$ adjacent to x‎ such that the function $\eta:V(G)\rightarrow {0,1,2,3}‎, ‎defined by‎ \eta(x)=\alpha‎, ‎$\eta(y)=h(y)-\alpha$‎, ‎where $\alpha\in\{1,2\}$‎, ‎and $\eta(z)=h(z)$ if‎ $z\in V(G)-\{x,y\}$ has no undefended vertex‎. ‎The weight of‎ ‎a GRD-function h is the value $\sum_{x\in V(G)}h(x)$‎, and the minimum weight of a GRD-function on G is‎ the generous Roman domination number (GRD-number) of G. ‎In this paper‎, ‎we determine the exact value of the GRD-number for the‎ ‎ladder graphs‎, ‎and we provide an upper bound on it for trees in terms of the‎ ‎order‎, ‎the number of leaves and the number of stems‎. ‎Moreover‎, ‎we‎ ‎show that for every tree on at least three vertices‎, ‎the GRD-number is bounded below by the domination number plus 2‎, ‎and we‎ characterize the extremal trees attaining this lower bound‎.

Keywords

Main Subjects

References

[1] I. Stewart, Defend the Roman Empire!, Sci. Am. 281 (1999) 136 - 139.
[2] C. S. ReVelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Am. Math. Mon. 107 (2000) 585 - 594, https://doi.org/10.2307/2589113.
[3] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11 - 22, https://doi.org/10.1016/j.disc.2003.06.004.
[4] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Roman domination in graphs. Topics in domination in graphs, (Eds), T.W. Haynes, S.T.Hedetniemi and M.A. Henning, Springer: Berlin/Heidelberg, Germany, 2020, 365 - 409.
[5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, structures of domination in graphs, (Eds), T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Springer: Berlin/Heidelberg, Germany,
(2021) 273 - 307.
[6] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020) 966 - 984, https://doi.org/10.1016/j.akcej.2019.12.001.
[7] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: a survey, Discuss. Math. Graph Theory 42 (2022) 861 - 891, https://doi.org/10.7151/dmgt.2313.
[8] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141 - 171.
[9] M. A. Henning and S. T. Hedetniemi, Defending the Roman Empire - A new strategy, Discrete Math. 266 (2003) 239-251, https://doi.org/10.1016/S0012-365X(02)00811-7.
[10] P. R. Leely Pushpam and T. Malini Mai, Weak Roman domination in graphs, Discuss. Math. Graph Theory 31 (2011) 161 -170.
[11] P. R. Leely Pushpam and N. Srilakshmi, Weak Roman domination stable graphs upon edge-addition, Commun. Comb. Optim. 8 (2023) 467 - 481, https://doi.org/ 10.22049/CCO.2022.27765.1348.
[12] A. Cabrera Martínez, L. P. Montejano and J. A. Rodríguez-Velázquez, Total weak Roman domination in graphs, Symmetry 11 (2019) #831, https://doi.org/10.3390/sym11060831.
[13] M. Valveny, H. Pérez-Rosés and J. A. Rodríguez-Velázquez, On the weak Roman domination number of lexicographic product graphs, Discret. Appl. Math. 263 (2019) 257 - 270, https://doi.org/10.1016/j.dam.2018.03.039.
[14] R. A. Beeler, T. W. Haynes and S. T. Hedetniemi, Double Roman domination, Discret. Appl. Math. 211 (2016) 23 - 29,
https://doi.org/10.1016/j.dam.2016.03.017.
[15] M. Benatallah, M. Blidia and L. Ouldrabah, The generous Roman domination number, Trans. Comb. 13 (2024) 179 - 196, https://doi.org/10.22108/TOC.2023.131167.1928.
[16] S. Soltani, H. A. Ahangar, M. Chellali, H. Rahbani and S. M. Sheikholeslami, Weak Double Roman Domination, Bull. Malays. Math. Sci. Soc. 47 (2024) #184, https://doi.org/10.1007/s40840-024-01782-5.
Mathematics Interdisciplinary Research
Volume 10, Issue 2
June 2025
Pages 231-243

Files

Share

How to cite

Statistics