Geodesic
Total 2-Rainbow Domination Numbers of Trees
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 345-364.

Voir la notice de l'article provenant de la source Library of Science

A 2-rainbow dominating function (2RDF) of a graph G = (V(G), E(G)) is a function f from the vertex set V(G) to the set of all subsets of the set 1, 2 such that for every vertex v ∈ V(G) with f(v) = ∅ the condition ⋃_u∈N(v)f(u) = {1, 2} is fulfilled, where N(v) is the open neighborhood of v. A total 2-rainbow dominating function f of a graph with no isolated vertices is a 2RDF with the additional condition that the subgraph of G induced by {v ∈ V (G) | f(v) ≠∅} has no isolated vertex. The total 2-rainbow domination number, γ_tr2(G), is the minimum weight of a total 2-rainbow dominating function of G. In this paper, we establish some sharp upper and lower bounds on the total 2-rainbow domination number of a tree. Moreover, we show that the decision problem associated with γ_tr2(G) is NP-complete for bipartite and chordal graphs.
Keywords: 2-rainbow dominating function, 2-rainbow domination number, total 2-rainbow dominating function, total 2-rainbow domination number 
@article{DMGT_2021_41_2_a0,
     author = {Ahangar, H. Abdollahzadeh and Amjadi, J. and Chellali, M. and Nazari-Moghaddam, S. and Sheikholeslami, S.M.},
     title = {Total {2-Rainbow} {Domination} {Numbers} of {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {345--364},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a0/}
}
TY  - JOUR
AU  - Ahangar, H. Abdollahzadeh
AU  - Amjadi, J.
AU  - Chellali, M.
AU  - Nazari-Moghaddam, S.
AU  - Sheikholeslami, S.M.
TI  - Total 2-Rainbow Domination Numbers of Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 345
EP  - 364
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a0/
LA  - en
ID  - DMGT_2021_41_2_a0
ER  - 
%0 Journal Article
%A Ahangar, H. Abdollahzadeh
%A Amjadi, J.
%A Chellali, M.
%A Nazari-Moghaddam, S.
%A Sheikholeslami, S.M.
%T Total 2-Rainbow Domination Numbers of Trees
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 345-364
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a0/
%G en
%F DMGT_2021_41_2_a0
Ahangar, H. Abdollahzadeh; Amjadi, J.; Chellali, M.; Nazari-Moghaddam, S.; Sheikholeslami, S.M. Total 2-Rainbow Domination Numbers of Trees. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 345-364. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a0/

[1] H. Abdollahzadeh Ahangar, J. Amjadi, N. Jafari Rad and V. Samodivkin, Total k-rainbow domination in graphs, Comm. Combin. Optim. 3 (2018) 37–50. doi:10.22049/CCO.2018.25719.1021

[2] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517. doi:10.2298/AADM160802017A

[3] H. Abdollahzadeh Ahangar, M. Khaibari, N. Jafari Rad and S.M. Sheikholeslami, Graphs with large total 2-rainbow domination number, Iran. J. Sci. Technol. Trans. A Sci. 42 (2018) 841–846. doi:10.1007/s40995-017-0465-9

[4] G.J. Chang, J. Wu and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010) 8–12. doi:10.1016/j.dam.2009.08.010

[5] M. Chellali and N. Jafari Rad, On 2-Rainbow domination and Roman domination in graphs, Australas. J. Combin. 56 (2013) 85–93.

[6] B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 201–213.

[7] B. Brešar and T.K. Sumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394–2400. doi:10.1016/j.dam.2007.07.018

[8] N. Dehgardi, S.M. Sheikholeslami and L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015) 102–114.

[9] E. DeLaVina, C.E. Larson, R. Pepper and B. Waller, On total domination and support vertices of a tree, AKCE Int. J. Graphs Comb. 7 (2010) 85–95.

[10] M. Falahat, S.M. Sheikholeslami and L. Volkmann, New bounds on the rainbow domination subdivision number, Filomat 28 (2014) 615–622. doi:10.2298/FIL1403615F

[11] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608–619. doi:10.1007/s10878-012-9482-y

[12] Y. Wu and N. Jafari Rad, Bounds on the 2-Rainbow domination number of graphs, Graphs Combin. 29 (2013) 1125–1133. doi:10.1007/s00373-012-1158-y

[13] Y. Wu and H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010) 706–709. doi:10.1016/j.aml.2010.02.012