2-Rainbow Domination Number of Some Graphs

Abstract

A 2-rainbow domination function of a graph G is a function f that assigns to each vertex a set of

colors chosen from the set {1,2}, such that for any 𝑣 ∈ 𝑉(𝐺), 𝑓(𝑣) = ∅ implies ⋃𝑢∈𝑁(𝑣) |𝑓(𝑣)| =

{1,2}. The 2-rainbow domination number 𝛾𝑟2(𝐺) of a graph G is minimum w(𝑓) = Σ𝑣∈𝑉(𝐺) |𝑓(𝑣)|

over all such functions f. In this paper, we show that upper bounds of 2-rainbow domination

numbers of several classes of graphs.

Keywords

• Vulnerability,domination,2-rainbow domination,k  th power of a graph

References

1. Brešar B.; Henning M.A.; Rall D.F.; Paired-domination of Cartesian Products of Graphs and Rainbow Domination, Electronic Notes in Discrete Mathematics, 2005; 22, 233-237.
2. Brešar B.; Henning M.A.; Rall D.F.; Rainbow Domination in Graphs, Taiwanese Journal of Mathematics, 2008; 12 (1), 213-225.
3. Bre𝑠̌𝑎𝑟 B.; 𝑆 ̌ umenjak T.K.; On the 2-rainbow Domination in Graphs, Discrete Applied Mathematics, 2007; 155, 2394- 2400.
4. Chartrand G.; Lesniak L.; Zhang P; Graphs and Digraphs, Chapman and Hall/CRC Press. 5 edition, 2010.
5. Tong C; Lin X; Yang Y; Luo M.; 2-Rainbow Domination of Generalized Petersen Graphs P(n,2), Discrete Applied Mathematics. 2009; 157, 1932-1937.
6. Xu G.; 2-Rainbow Domination in Generalized Petersen Graphs P(n,3), Discrete Applied Mathematics, 2009; 157, 2570-2573.
7. Shao Z.; Liang M., On Rainbow Domination Number of Graphs, Information Sciences, 2014; 254, 225-234.