On mixed double Roman domination number and 2-independence number of graphs

Document Type : Full Length Article

Authors

1 Department of Mathematics, Tafresh University, Tafresh, Iran.

2 Tafresh University

3 Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran.

Abstract

Let G=(V(G),E(G)) be a simple graph. A mixed double Roman dominating function (MDRDF) on G is a function f:V(G)∪E(G) → {0,1,2,3} such that (i) if f(u)=0, then u has at least two neighbors assigned 2 under f or one neighbor w with f(w)=3; (ii) if f(u)=1, then u must have at least one neighbor w with f(w)≥ 2. The weight of f is equal to Σu∈V(G)∪E(G)f(u). The mixed double Roman domination number γdR*(G) is the minimum weight among all MDRDF's of G. A subset X of V(G) is a 2-independent set of G if the subgraph induced by the vertices of X is isomorphic to rK2∪sK1, where 2r+s=|X|. The maximum cardinality of a 2-independent set of G is the 2-independence number β2(G). In this paper, it is shown that these parameters are incomparable, in general. Also, we prove that either T is a path or a tree with a quasi-diagonal path u1,…, uk such that d(u2)≠ 2 or d(u3)≠ 2, then γdR*(T)≤ 2β2(T). Moreover, all extremal trees in this family that attaining equality are characterized.

Graphical Abstract

On mixed double Roman domination number and 2-independence number of graphs

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Kosari, V. Samodivkin, S. M. Sheikholeslami,
Some progress on the mixed Roman domination in graphs, RAIRO-Oper. Res. 55 (2021) 1411–1423.
https://doi.org/10.1051/ro/2020038
[2] H. Abdollahzadeh Ahangar, M. Chellai, S. M. Sheikholeslam, On the double Roman domination in
graphs, Discrete Appl. Math. 232 (2017) 1–7. https://doi.org/10.1016/J.DAM.2017.06.014
[3] H. Abdollahzadeh Ahangar,Teresa W. Haynes, J. C. Valenzuela-Tripodoro, Mixed Roman domination
in graphs, Bull. Malays. Math. Sci. Soc. 40 (2017) 1443–1454. https://doi.org/10.1007/s40840-015-
0141-1
[4] J. Amjadi, N. Dehgardi, S. M. Sheikholeslami, M. Valinavaz, Independent Roman domination and
2-independence in trees, Discrete Math. Algorithms Appl. 10(4) (2018). https://doi.org/ 10.1142/
S1793830918500520
[5] V. Anu, S. Aparna Lakshmanan, Double Roman domination number, Discret. Appl. Math. 244
(2018) 198–204. https://doi.org/10.1016/j.dam.2018.03.026
[6] S. Banerjee, M. A. Henning, D. Pradhan, Algorithmic results on double Roman domination in
graphs, J. Comb. Optim. 39 (2020) 90–114. https://doi.org/10.1007/s10878-019-00457-3
[7] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Roman Domination in graphs, In
Topics in Domination in Graphs; T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Eds.; Springer
International Publishing: Cham, Switzerland (2020) 365–409.
[8] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination, In
Structures of Domination in Graphs; T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Eds.; Springer
International Publishing: Cham, Switzerland (2021) 273–307.
[9] 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
[10] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann,Chellali, 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
[11] X. G. Chen, A note on the double Roman domination number of graphs, Czechoslov. Math. J. 70
(2020) 205–212. https://doi.org/10.21136/CMJ.2019.0212-18
[12] 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
[13] N. Dehgardi, Mixed Roman domination and 2-independence in trees, Commun. Comb. Optim. 3(1)
(2018) 79–91. https://doi.org/10.22049/cco.2018.25964.1062
[14] O. Favaron, H. Karami, R. Khoeilar, S. M. Sheikholeslami, On the Roman domination number of a
graph, Discrete Math. 309 (2009) 3447–3451. https://doi.org/10.1016/j.disc.2008.09.043
[15] J. F. Fink, M. S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in Graph
Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York,
(1985) 301–311.
[16] G. Hao, L. Volkmann, D. A. Mojdeh, Total double Roman domination in graphs, Commun. Combin.
Optim. 5(1) (2020) 27–39. https://doi.org/10.22049/cco.2019.26484.1118
[17] M. A. Henning, Defending the Roman empire from multiple attacks, Discrete Math. 271 (2003)
101–115. https://doi.org/10.1016/S0012-365X(03)00040-2
[18] H. Koulivand, M. Habibi, H. Arianpoor, M. Valinavaz, Independent double Roman domination
number of a tree in terms of its 2-independence number, Discrete Math. Algorithms Appl. 18(3)
(2026) 2550047. https://doi.org/10.1142/S1793830925500478
[19] N. Meddah, M. Chellali, Roman domination and 2-independence in trees, Discrete Math. Algorithms
Appl. 9 (2017) 1750023. https://doi.org/10.1142/S1793830917500239
[20] D. A. Mojdeh, A. Parsian, I. Masoumi, Characterization of double Roman trees, Ars Comb. 153
(2020) 53–68.
[21] D. A. Mojdeh, A. Parsian, I. Masoumi, Strong Roman domination number of complementary prism
graphs, Turkish J. Math. Comput. Sci. 11(1) (2019) 40–47.
[22] D. A. Mojdeh, B. Samadi, Z. Shao, I. G. Yero, On the outer independent double Roman domination
number, Bull. Iran. Math. Soc. 48(4) (2022) 1789–1803. https://doi.org/10.1007/s41980-021-00606-7
[23] L. Ouldrabah, L. Volkmann, An Upper bound on the double Roman domination number, Bull. Iran.
Math. Soc. 47 (2021) 1315–1323. https://doi.org/10.1007/s10878-018-0286-6
[24] 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
[25] I. Stewart, Defend the Roman empire!, Sci. Amer. 281(6) (1999) 136–139. https://doi.org/ 10.1038/
SCIENTIFICAMERICAN1299-136
[26] A. Teymourzadeh, D. A. Mojdeh, Covering total double Roman domination in graphs, Commun.
Combin. Optim. 8(1) (2023) 115–125. https://doi.org/10.22049/cco.2021.27443.1265
[27] M. Valinavaz, Mixed double Roman domination number of a graph, Commun. Combin. Cryptogr.
and Computer Sci. 2 (2022) 167–174.
[28] M. Valinavaz, Mixed double Roman domination number in trees, Commun. Combin. Cryptogr. and
Computer Sci. 2 (2022) 175–180.
[29] J. Yue, M. Wei, M. Li, G. Liu, On the double Roman domination of graphs, Appl. Math. Comput.
338 (2018) 669–675. https://doi.org/10.1016/j.amc.2018.06.033
[30] X. Zhang, Z. Li, H. Jiang, Z. Shao, Double Roman domination in trees, Inf. Process. Lett. 134 (2018)
31–34. https://doi.org/10.1016/j.ipl.2018.01.004
Journal of Discrete Mathematics and Its Applications
Volume 11, Issue 3
September 2026
Pages 163-175

Files

History

  • Receive Date: 05 October 2025
  • Revise Date: 22 January 2026
  • Accept Date: 27 January 2026
  • First Publish Date: 30 August 2026
  • Publish Date: 01 September 2026

Share

How to cite

Statistics