Generous Roman domination stability in graphs

Document Type : Full Length Article

Authors

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

2 LAMDA-RO Laboratory, Department of Mathematics, University of Blida

Abstract

Let G=(V, E) be a simple graph and f a function defined from V to {0,1,2,3}. A vertex u with f(u)=0 is called an undefended vertex with respect to f if it is not adjacent to a vertex v with f(v) ≥ 2. The function f is called a generous Roman dominating function (GRD-function) if for every vertex with f(u)=0 there exists at least a vertex v with f(v) ≥ 2 adjacent to u such that the function f': V→{0,1,2,3}, defined by f'(u)=α, f'(v)=f(v)-α, where α∈{1,2}, and f'(w)=f(w) if w∈ V-{u,v} has no undefended vertex. The weight of a GRD-function f is the sum of its function values over all vertices, and the minimum weight of a GRD-function on G is the generous Roman domination number ϒgR(G). The ϒgR(G)-stability st_ϒgR(G) (resp. ϒgR--stability st_ϒgR-(G), ϒgR+-stability st_ϒgR+(G) of  G is defined as the order of the smallest set of vertices whose removal changes (resp. decreases, increases) the generous Roman domination number. In this paper, we first determine the exact values of ϒgR-stability for some special classes of graphs, and then we present some bounds on st_ϒgR(G). We also characterize graphs with large st_ϒgR(G). Moreover, we show that if T is a nontrivial tree, then st_{ϒgR}(T) ≤ 2, and if further T has maximum degree Δ ≥ 3, then st_{ϒgR-(T)} ≤ Δ-1.

Keywords

Main Subjects

References

[1] A. A. Aghdash, N. Jafari Rad, B.V. Fasaghandisi, On the restrained domination stability in graphs,
RAIRO-Oper. Res. 59 (2025) 579–586. https://doi.org/10.1051/ro/2024233
[2] D. Bauer, F. Harary, J. Nieminen, C. Suffel, Domination alternation sets in graphs, Discrete Math.
47 (1983) 153–161. https://doi.org/10.1016/0012-365X(83)90085-7
[3] M. Benatallah, M. Blidia, L. Ouldrabah, The generous Roman domination number, Trans. Comb.
13 (2024) 179–196. https://doi.org/10.22108/toc.2023.131167.1928
[4] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, 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) 365–409. https://doi.org/10.1007/978-3-030-51117-3
[5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, 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) 273–307. https://doi.org/10.1007/978-3-030-58892-2 10
[6] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, 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, L. Volkmann, Varieties of Roman domination III,
submitted.
[8] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, 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
[9] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, A survey on Roman domination
parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141–171. https://
combinatorialpress.com/ jcmcc-articles/ volume-115
[10] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, S. T. Hedetniemi, Roman domination in graphs,
Discrete Math. 278 (2004) 11–22. https://doi.org/10.1016/j.disc.2003.06.004
[11] N. Jafari Rad, E. Sharifi, M. Krzywkowski, Domination stability in graphs, Discrete Math. 339
(2016) 1909–1914. https://doi.org/10.1016/j.disc.2015.12.026
[12] M. Hajian, N. Jafari Rad, On the Roman domination stable graphs, Discuss. Math. Graph Theory
37 (2017) 859–871. https://doi.org/10.7151/dmgt.1975
[13] A. Kemnitz, M. Marangio, Edge adding stability of graphs, Commun. Comb. Optim. In press
(2025) https://doi.org/10.22049/cco.2025.30108.2313
[14] C. S. ReVelle, K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy,
Amer. Math. Monthly 107 (7) (2000) 585–594. https://doi.org/10.1080/00029890.2000.12005243
[15] S. M. Sheikholeslami, M. Esmaeili, J. J. Hamja, C. L. Armada, I. S. Aniversario, Independent double
Roman domination stability in graphs, Euro. J. Pure Appl. Math. 18 (2025) 5984. https:// doi.org/
10.29020/ nybg.ejpam.v18i2.5984
[16] S. M. Sheikholeslami, M. Esmaeili, L. Volkmann, Outer independent double Roman domination
stability in graphs, Ars Combin. 160 (2024) 21–29. https:// doi.org/ 10.61091/ ars-160-04
[17] S. M. Sheikholeslami, M. Chellali, M. Kor, Further results on generous Roman domination, Math.
Interdisc. Res. 10(2) (2025) 231–243. https://doi.org/10.22052/mir.2025.256617.1511
[18] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281(6) (1999) 136–139. https://doi.org/
10.1038/scientificamerican1299-136
[19] Z. Xu, S. Kosari, M. Esmaeili, A. Khan, L. Volkmann, Total double Roman domination stability in
graphs, Commun. Comb. Optim. In press (2025) https://doi.org/10.22049/cco.2025.30402.2453
[20] W. Zhuang, Double Roman domination stability in graphs, Discrete Appl. Math. 371 (2025) 254–
263. https://doi.org/10.1016/j.dam.2025.04.035
Journal of Discrete Mathematics and Its Applications
Volume 11, Issue 1
March 2026
Pages 1-12

Files

History

  • Receive Date: 06 March 2025
  • Revise Date: 25 April 2025
  • Accept Date: 25 April 2025
  • First Publish Date: 08 July 2025
  • Publish Date: 01 March 2026

Share

How to cite

Statistics