Bounds for signed double Roman k-domination in trees

Yang, Hong; Wu, Pu; Nazari-Moghaddam, Sakineh; Sheikholeslami, Seyed Mahmoud; Zhang, Xiaosong; Shao, Zehui; Tang, Yuan Yan

doi:10.1051/ro/2018043

Yang, Hong ¹ ; Wu, Pu ¹ ; Nazari-Moghaddam, Sakineh ¹ ; Sheikholeslami, Seyed Mahmoud ¹ ; Zhang, Xiaosong ¹ ; Shao, Zehui ¹ ; Tang, Yuan Yan ¹

¹

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

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.

Résumé

Let $k \geq 1$ be an integer and $G$ be a simple and finite graph with vertex set $V (G)$ . A signed double Roman $k$ -dominating function (SDR $k$ DF) on a graph $G$ is a function $f : V (G) \to {- 1, 1, 2, 3}$ such that (i) every vertex $v$ with $f (v) = - 1$ is adjacent to at least two vertices assigned a 2 or to at least one vertex $w$ with $f (w) = 3$ , (ii) every vertex $v$ with $f (v) = 1$ is adjacent to at least one vertex $w$ with $f (w) \geq 2$ and (iii) $\sum_{u \in N [v]} f (u) \geq k$ holds for any vertex $v$ .The weight of a SDR $k$ DF $f$ is $\sum_{u \in V (G)} f (u)$ , and the minimum weight of a SDR $k$ DF is the signed double Roman $k$ -domination number $γ_{s d R}^{k}$ of $G$ .In this paper, we investigate the signed double Roman $k$ -domination number of trees. In particular, we present lower and upper bounds on $γ_{s d R}^{k} (T)$ for $2 \leq k \leq 6$ and classify all extremal trees.

MR Zbl

DOI : 10.1051/ro/2018043

Classification : 05C69

Affiliations des auteurs :

Yang, Hong ¹ ; Wu, Pu ¹ ; Nazari-Moghaddam, Sakineh ¹ ; Sheikholeslami, Seyed Mahmoud ¹ ; Zhang, Xiaosong ¹ ; Shao, Zehui ¹ ; Tang, Yuan Yan ¹

¹

@article{RO_2019__53_2_627_0,
     author = {Yang, Hong and Wu, Pu and Nazari-Moghaddam, Sakineh and Sheikholeslami, Seyed Mahmoud and Zhang, Xiaosong and Shao, Zehui and Tang, Yuan Yan},
     title = {Bounds for signed double {Roman} k-domination in trees},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {627--643},
     year = {2019},
     publisher = {EDP Sciences},
     volume = {53},
     number = {2},
     doi = {10.1051/ro/2018043},
     mrnumber = {3959475},
     zbl = {1440.05164},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2018043/}
}

TY  - JOUR
AU  - Yang, Hong
AU  - Wu, Pu
AU  - Nazari-Moghaddam, Sakineh
AU  - Sheikholeslami, Seyed Mahmoud
AU  - Zhang, Xiaosong
AU  - Shao, Zehui
AU  - Tang, Yuan Yan
TI  - Bounds for signed double Roman k-domination in trees
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 627
EP  - 643
VL  - 53
IS  - 2
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2018043/
DO  - 10.1051/ro/2018043
LA  - en
ID  - RO_2019__53_2_627_0
ER  -

%0 Journal Article
%A Yang, Hong
%A Wu, Pu
%A Nazari-Moghaddam, Sakineh
%A Sheikholeslami, Seyed Mahmoud
%A Zhang, Xiaosong
%A Shao, Zehui
%A Tang, Yuan Yan
%T Bounds for signed double Roman k-domination in trees
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 627-643
%V 53
%N 2
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro/2018043/
%R 10.1051/ro/2018043
%G en
%F RO_2019__53_2_627_0

Yang, Hong; Wu, Pu; Nazari-Moghaddam, Sakineh; Sheikholeslami, Seyed Mahmoud; Zhang, Xiaosong; Shao, Zehui; Tang, Yuan Yan. Bounds for signed double Roman k-domination in trees. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 627-643. doi: 10.1051/ro/2018043

Bibliographie
Cité par

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Atapour, M. Chellali and S.M. Sheikholeslami, Double roman trees. To appear in: Ars Combin. (2019). | MR | Zbl

[2] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam and S.M. Sheikholeslami, Trees with double Roman domination number twice the domination number plus two. To appear in: Iran. J. Sci. Technol. Trans. A Sci. (2019). | MR

[3] H. Abdollahzadeh Ahangar, M. Chellali and S.M. Sheikholeslami, On the double Roman domination in graphs. Discrete Appl. Math. 232 (2017) 1–7. | MR | Zbl

[4] H. Abdollahzadeh Ahangar, M. Chellali and S.M. Sheikholeslami, Signed double Roman domination in graphs. Discrete Appl. Math. 257 (2019) 1–11. | MR | Zbl

[5] H. Abdollahzadeh Ahangar, M.A. Henning, C. Löwenstein, Y. Zhao and V. Samodivkin, Signed Roman domination in graphs. J. Comb. Optim. 27 (2014) 241–255. | MR | Zbl

[6] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami and L. Volkmann, An upper bound on the double Roman domination number. J. Comb. Optim. 36 (2018). Doi: 10.1007/s10878-018-0286-6. | MR | Zbl

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

[8] O. Favaron, Signed domination in regular graphs. Discrete Math. 158 (1996) 287–293. | MR | Zbl

[9] M.A. Henning and L. Volkmann, Signed Roman k-domination in graphs. Graphs Combin. 32 (2016) 175–190. | MR | Zbl

[10] M.A. Henning and L. Volkmann, Signed Roman k-domination in trees. Discrete Appl. Math. 186 (2015) 98–105. | MR | Zbl

[11] A. Mahmoodi, On the signed Roman edge k-domination in graphs. Commun. Comb. Optim. 2 (2017) 57–64. | MR | Zbl

[12] Z. Shao, S. Klavzar, Z. Li, P. Wu and J. Xu, On the signed Roman k-domination: complexity and thin torus graphs. Discrete Appl. Math. 233 (2017) 175–186. | MR | Zbl

[13] S.M. Sheikholeslami and L. Volkmann, The signed Roman domatic number of a digraph. Electron. J. Graph Theory Appl. 3 (2015) 85–93. | MR | Zbl

[14] S.M. Sheikholeslami and L. Volkmann, Signed Roman domination number in digraphs. J. Comb. Optim. 30 (2015) 456–467. | MR | Zbl

[15] L. Volkmann, The double Roman domatic number of a graph. J. Combin. Math. Combin. Comput. 104 (2018) 205–215. | MR | Zbl

[16] L. Volkmann, Double Roman domination and domatic numbers of graphs. Commun. Comb. Optim. 3 (2018) 71–77. | MR | Zbl

[17] L. Volkmann, The signed Roman k-domatic number of a graph. Discrete Appl. Math. 180 (2015) 150–157. | MR | Zbl

[18] L. Volkmann, Signed Roman k-domination in digraphs. Graphs Combin. 32 (2016) 1217–1227. | MR | Zbl

[19] L. Volkmann, The signed Roman k-domatic number of digraphs. Aust. J. Combin. 64 (2016) 444–457. | MR | Zbl

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

Cité par Sources :