no. 4
Restrained double Roman domination of a graph
RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2293-2304

For a graph G = (V, E), a restrained double Roman dominating function is a function f : V → {0, 1, 2, 3} having the property that if f(v) = 0, then the vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then the vertex v must have at least one neighbor w with f(w) ≥ 2, and at the same time, the subgraph G[V0] which includes vertices with zero labels has no isolated vertex. The weight of a restrained double Roman dominating function f is the sum f(V) = ∑$$f(v), and the minimum weight of a restrained double Roman dominating function on G is the restrained double Roman domination number of G. We initiate the study of restrained double Roman domination with proving that the problem of computing this parameter is NP-hard. Then we present an upper bound on the restrained double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. We study the restrained double Roman domination versus the restrained Roman domination. Finally, we investigate the bounds for the restrained double Roman domination of trees and determine trees T attaining the exhibited bounds.

DOI : 10.1051/ro/2022089
Keywords: 05C69, Domination, restrained Roman domination, restrained double Roman domination 
@article{RO_2022__56_4_2293_0,
     author = {Mojdeh, Doost Ali and Masoumi, Iman and Volkmann, Lutz},
     title = {Restrained double {Roman} domination of a graph},
     journal = {RAIRO. Operations Research},
     pages = {2293--2304},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {4},
     doi = {10.1051/ro/2022089},
     mrnumber = {4458843},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022089/}
}
TY  - JOUR
AU  - Mojdeh, Doost Ali
AU  - Masoumi, Iman
AU  - Volkmann, Lutz
TI  - Restrained double Roman domination of a graph
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 2293
EP  - 2304
VL  - 56
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022089/
DO  - 10.1051/ro/2022089
LA  - en
ID  - RO_2022__56_4_2293_0
ER  - 
%0 Journal Article
%A Mojdeh, Doost Ali
%A Masoumi, Iman
%A Volkmann, Lutz
%T Restrained double Roman domination of a graph
%J RAIRO. Operations Research
%D 2022
%P 2293-2304
%V 56
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022089/
%R 10.1051/ro/2022089
%G en
%F RO_2022__56_4_2293_0
Mojdeh, Doost Ali; Masoumi, Iman; Volkmann, Lutz. Restrained double Roman domination of a graph. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2293-2304. doi: 10.1051/ro/2022089

[1] V. Anu and A. Lakshmanan, Double Roman domination number. Discret. Appl. Math. 244 (2018) 198–204. | MR | DOI

[2] J. Arquilla and H. Fredricksen, “Graphing” – An Optimal Grand Strategy. Mil. Oper. Res. 1 (1995) 3–17. | DOI

[3] R. A. Beeler, T. W. Haynes and S. T. Hedetniemi, Double Roman domination. Discret. Appl. Math. 211 (2016) 23–29. | MR | DOI

[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. A. Mcraee, Roman { 2 } -domination. Discret. Appl. Math. 204 (2016) 22–28. | MR | DOI

[5] X. Chen, J. Liu and J. Meng, Total restrained domination in graphs. Comput. Math. Appl. 62 (2011) 2892–2898. | MR | DOI

[6] G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar and L. R. Markus, Restrained domination in graphs. Discret. Math. 203 (1999) 61–69. | MR | DOI

[7] J. Hattingh and E. Joubert, Restrained domination in cubic graphs. J. Comb. Optim. 22 (2011) 166–179. | MR | DOI

[8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in graphs. New York: Marcel Dekker (1998). | MR

[9] M. Henning, Graphs with large restrained domination number. Discret. Math. 197198 (1999) 415–429. | MR | DOI

[10] M. A. Henning, Defending the Roman Empire from multiple attacks. Discret. Math. 271 (2003) 101–115. | MR | DOI

[11] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs. Discuss. Math. Graph Theory 39 (2018) 41–53. | MR | DOI

[12] R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1972) (1972) 85–103. | MR

[13] D. A. Mojdeh and L. Volkmann, Roman { 3 } -domination (double Italian domination). Discret. Appl. Math. 283 (2020) 555–564. | MR | DOI

[14] C. S. Revelle and K. E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy. Am. Math. Mon. 107 (2000) 585–594. | MR | DOI

[15] P. Roushini Leely and C. Suseendran, Secure restrained domination in Graphs. Math. Comput. Sci. 9 (2015) 239–247. | MR | DOI

[16] P. Roushini Leely and S. Padmapriea, Restrained Roman domination in graphs. Trans. Comb. 4 (2015) 1–17. | MR

[17] B. Samadi, M. Alishahi, I. Masoumi and D. A. Mojdeh, Restrained Italian domination in graphs. RAIRO: OR 55 (2021) 319–332. | MR | Zbl | Numdam | DOI

[18] I. Stewart, Defend the Roman Empire. Sci. Am. 281 (1999) 136–138. | DOI

[19] Z. Tahmasbzadehbaee, D. S. Nandappa, H. A. Ahangar, D. A. Mojdeh and Y. Zhao, Total restrained domination in graphs of diameter 2 or 3. Math. Sci. 7 (2013) 26. | MR | DOI

[20] D. B. West, in Introduction to Graph Theory, 2nd edition. Prentice Hall (2001). | MR

[21] X. Zhang, Z. Li, H. Jiang and Z. Shao, Double Roman domination in trees. Inf. Process. Lett. 134 (2018) 31–34. | MR | DOI

Cité par Sources :