Total double Roman domination stability in graphs

Articles in Press

Document Type : Original paper

Authors

1 Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

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

3 University of Technology and Applied Sciences, Musannah, Oman

4 RWTH Aachen, 52056 Aachen, Germany

Abstract

Let G be a graph with vertex set V(G). A total double Roman dominating function (TDRD-function) on a graph G with no isolated vertices is a function f:V(G)→{0,1,2,3} satisfying the conditions: (i) if f(v)=0, then the vertex v must be adjacent to at least two vertices assigned 2 or one vertex assigned 3 under f, and if f(v)=1, then the vertex v must be adjacent to at least one vertex assigned 2 or 3 and (ii) the subgraph of G induced by the set {v∈V(G)∣f(v)≠0} has no isolated vertices. The weight of a TDRD-function f is the sum of its function values over all vertices, and the minimum weight of a TDRD-function on G is the total double Roman domination number, γtdR(G). The γtdR-stability (γtdR−-stability, γtdR+-stability) of G, denoted by stγtdR(G) (resp. stγtdR−(G), stγtdR+(G)), is defined as the minimum size of a set of vertices whose removal changes (resp. decreases, increases) the total double Roman domination number. In this paper, we first determine the exact values of the γtdR-stability of some special classes of graphs, and then we present some bounds on stγtdR(G),  st−γtdR(G) and stγtdR+(G)). In particular, for a graph G with maximum degree Δ≥3, we show that stγtdR−(G)≤Δ−1.

Keywords

Main Subjects

References

[1] A.A. Aghdash, N. Jafari Rad, and B.V. Fasaghandisi, On the restrained domination stability in graphs, RAIRO Oper. Res. 59 (2025), no. 1, 579–586.  https://doi.org/10.1051/ro/2024233
[2] M. Akhoundi, A. Khan, J. Shafi, and L. Volkmann, Quasi total double Roman domination in trees, Commun. Comb. Optim. 9 (2024), no. 1, 159–168. https://doi.org/10.22049/cco.2023.29008.1809
[3] D. Bauer, F. Harary, J. Nieminen, and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161.  https://doi.org/10.1016/0012-365X(83)90085-7
[4] 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 International Publishing, Cham, 2020, pp. 365–409.
[5] 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.
[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, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory 42 (2022), no. 3, 861–891.
[8] 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 International Publishing, Cham,
2021, pp. 273–307.
[9] 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
[10] M. Hajian and N. Jafari Rad, On the Roman domination stable graphs, Discuss. Math. Graph Theory 37 (2017), no. 4, 859–871.  http://dx.doi.org/10.7151/dmgt.1975
[11] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.  https://doi.org/10.22049/cco.2019.26484.1118
[12] G. Hao, Z. Xie, S.M. Sheikholeslami, and M. Hajjari, Bounds on the total double Roman domination number of graphs, Discuss. Math. Graph Theory 43 (2023),  no. 4, 1033–1061.  https://doi.org/10.7151/dmgt.2417
[13] N. Jafari Rad, E. Sharifi, and M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (2016), no. 7, 1909–1914.  https://doi.org/10.1016/j.disc.2015.12.026
[14] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Am. Math. Mon. 107 (2000), no. 7, 585–594.  https://doi.org/10.1080/00029890.2000.12005243
[15] S.M. Sheikholeslami, M. Esmaeili, and L. Volkmann, Outer independent double Roman domination stability in graphs, Ars Combin. 160 (2024), 21–29.  http://dx.doi.org/10.61091/ars-160-04
[16] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[17] A. Teymourzadeh and D.A. Mojdeh, Covering total double Roman domination in graphs, Commun. Comb. Optim. 8 (2023), no. 1, 115–125.  https://doi.org/10.22049/cco.2021.27443.1265
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 June 2025

Files

Share

How to cite

Statistics