Trees with equal Roman {2}-domination number and independent Roman {2}-domination number

Wu, Pu; Li, Zepeng; Shao, Zehui; Sheikholeslami, Seyed Mahmoud

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 389-400

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

A Roman {2}-dominating function $\left(R2DF\right)$ on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f\left(u\right)=0$ is adjacent to either at least one vertex $v$ with $f\left(v\right)=2$ or two vertices $v_1{v}_2$ with $f\left(v_1\right)=f\left(v_2\right)=1$. The weight of an $\mathrm{R}\left\{2\right\}\mathrm{DF}f$ is the value $w\left(f\right)={\sum }_{u\in v}f\left(u\right)$. The minimum weight of an $R\left\{2\right\}\mathrm{DF}$ on a graph $G$ is called the Roman $\left\{2\right\}$-domination number ${\gamma }_{\left\{R2\right\}}\left(G\right)$ of $G$. An $\mathrm{R}\left\{2\right\}\mathrm{DF}f$ is called an independent Roman $\left\{2\right\}$-dominating function $\left(IR\right\{2\left\}DF\right)$ if the set of vertices with positive weight under $f$ is independent. The minimum weight of an $IR\left\{2\right\}DF$ on a graph $G$ is called the independent Roman $\left\{2\right\}$-domination number $i_{\left\{R2\right\}}\left(G\right)$ of $G$. In this paper, we answer two questions posed by Rahmouni and Chellali.

Classification : 05C69
Keywords: Roman {2}-domination, independent Roman {2}-domination, tree, algorithm

J.D. Alvarado, S. Dantas and D. Rautenbach, Strong equality of Roman and weak Roman domination in trees. Dis. Appl. Math. 208 (2016) 19–26. | Zbl

M.P. Álvarez-Ruiz, I. González Yero, T. Mediavilla-Gradolph, S.M. Sheikholeslami and J.C. Valenzuela, On the strong Roman domination number of graphs. Dis. Appl. Math. 231 (2017) 44–59. | Zbl

M. Atapour, S.M. Sheikholeslami and L. Volkmann, Global Roman domination in trees. Graphs Comb. 31 (2015) 813–825. | Zbl

E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination. SIAM J. Dis. Math. 23 (2009) 1575–1586. | Zbl

M. Chellali, T.W. Haynes and S.T. Hedetniemi, Lower bounds on the Roman and independent Roman domination numbers. Appl. Anal. Disc. Math. 10 (2016) 65–72. | Zbl

M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. Macrae, Roman {2}-domination. Dis. Appl. Math. 204 (2016) 22–28. | Zbl

E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs. Dis. Math. 278 (2004) 11–22. | Zbl

O. Favaron, H. Karami, R. Khoeilar and S.M. Sheikholeslami, On the Roman domination number of a graph. Dis. Math. 309 (2009) 3447–3451. | Zbl

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York, NY (1998). | Zbl

M.A. Henning and S.T. Hedetniemi, Defending the Roman empire – a new strategy. Dis. Math. 266 (2003) 239–251. | Zbl

M.A. Henning and W.F. Klostermeyer, Italian domination in trees. Dis. Appl. Math. 217 (2017) 557–564. | Zbl

O. Ore, Theory of Graphs. American Mathematical Society, Providence, RI (1967). | Zbl

A. Rahmouni and M. Chellali, Independent Roman {2}-domination in graphs. Dis. Appl. Math. 236 (2018) 408–414. | Zbl

Z. Shao, S. Klavžar, Z. Li, P. Wu and J. Xu, On the signed Roman k-domination: complexity and thin torus graphs. Dis. Appl. Math. 233 (2017) 175–186. | Zbl

Z. Shao, S.M. Sheikholeslami, M. Soroudi, L. Volkmann and X. Liu, On the co-Roman domination in graphs. Discuss. Math. Graph Theory 39 (2018) 455–472. | Zbl