Geodesic
Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 709-726.

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

A 2-rainbow dominating function (2RDF) of a graph G is a function g from the vertex set V (G) to the family of all subsets of {1, 2} such that for each vertex v with g(v) =∅ we have ⋃_u∈N(v) g(u) = { 1, 2 }. The minimum of g(V (G)) = Σ_v ∈ V (G) |g(v)| over all such functions is called the 2-rainbow domination number. A 2RDF g of a graph G is independent if no two vertices assigned non empty sets are adjacent. The independent 2-rainbow domination number is the minimum weight of an independent 2RDF of G. A Roman 2-dominating function (R2DF) f : V →{ 0, 1, 2 } of a graph G = (V, E) has the property that for every vertex v ∈ V with f(v) = 0 either there is u ∈ N(v) with f(u) = 2 or there are x, y ∈ N(v) with f(x) = f(y) = 1. The weight of f is the sum f(V) = Σ_v ∈ V f(v). An R2DF f is called independent if no two vertices assigned non-zero values are adjacent. The independent Roman 2-domination number is the minimum weight of an independent R2DF on G. We first show that the decision problem for computing the independent 2-rainbow (respectively, independent Roman 2-domination) number is NP-complete even when restricted to planar graphs. Then, we give a linear algorithm that computes the independent 2-rainbow domination number as well as the independent Roman 2-domination number of a given tree, answering problems posed in [M. Chellali and N. Jafari Rad, Independent 2-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015) 133–148] and [A. Rahmouni and M. Chellali, Independent Roman 2-domination in graphs, Discrete Appl. Math. 236 (2018) 408–414]. Then, we give a linear algorithm that computes the independent 2-rainbow domination number of a given unicyclic graph.
Keywords: independent 2-rainbow dominating function, independent Roman {2}-dominating function, algorithm, 3-SAT 
@article{DMGT_2022_42_3_a1,
     author = {Poureidi, Abolfazl and Rad, Nader Jafari},
     title = {Algorithmic {Aspects} of the {Independent} {2-Rainbow} {Domination} {Number} and {Independent} {Roman} {{2}-Domination} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {709--726},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/}
}
TY  - JOUR
AU  - Poureidi, Abolfazl
AU  - Rad, Nader Jafari
TI  - Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 709
EP  - 726
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/
LA  - en
ID  - DMGT_2022_42_3_a1
ER  - 
%0 Journal Article
%A Poureidi, Abolfazl
%A Rad, Nader Jafari
%T Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 709-726
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/
%G en
%F DMGT_2022_42_3_a1
Poureidi, Abolfazl; Rad, Nader Jafari. Algorithmic Aspects of the Independent 2-Rainbow Domination Number and Independent Roman {2}-Domination Number. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 709-726. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a1/

[1] J. Amjadi, M. Falahat, N. Jafari Rad and S.M. Sheikholeslami, Strong equality between the 2 -rainbow domination and independent 2 -rainbow domination numbers in trees, Bull. Malays. Math. Sci. Soc. 39 (2016) 205–218. https://doi.org/10.1007/s40840-015-0284-0

[2] B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213–225. https://doi.org/10.11650/twjm/1500602498

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

[4] M. Chellali and N. Jafari Rad, Independent 2 -rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015) 133–148

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

[6] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. MacRae, Roman {2} -domination, Discrete Appl. Math. 204 (2016) 22–28. https://doi.org/10.1016/j.dam.2015.11.013

[7] H. Chen and Ch. Lu, A note on Roman {2}-domination problem in graphs . arXiv:1804.09338.pdf

[8] E.J. Cockayane, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. https://doi.org/10.1016/j.disc.2003.06.004

[9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, New York, 1979).

[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[11] D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343. https://doi.org/10.1137/0211025

[12] A. Rahmouni and M. Chellali, Independent Roman {2} -domination in graphs, Discrete Appl. Math. 236 (2018) 408–414. https://doi.org/10.1016/j.dam.2017.10.028

[13] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594. https://doi.org/10.1080/00029890.2000.12005243

[14] Z. Shao, Z. Li, A. Peperko, J. Wan and J.Žerovnik, Independent rainbow domination of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 417–435. https://doi.org/10.1007/s40840-017-0488-6

[15] Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlič and J.Žerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014) 225–234. https://doi.org/10.1016/j.ins.2013.07.020

[16] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999) 136–139. https://doi.org/10.1038/scientificamerican1299-136

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