Opuscula Math. 36, no. 5 (2016), 563-574
http://dx.doi.org/10.7494/OpMath.2016.36.5.563

Opuscula Mathematica

# Criticality indices of 2-rainbow domination of paths and cycles

Ahmed Bouchou
Mostafa Blidia

Abstract. A $$2$$-rainbow dominating function of a graph $$G\left(V(G),E(G)\right)$$ is a function $$f$$ that assigns to each vertex a set of colors chosen from the set $$\{1,2\}$$ so that for each vertex with $$f(v)=\emptyset$$ we have $${\textstyle\bigcup_{u\in N(v)}} f(u)=\{1,2\}$$. The weight of a $$2$$RDF $$f$$ is defined as $$w\left( f\right)={\textstyle\sum\nolimits_{v\in V(G)}} |f(v)|$$. The minimum weight of a $$2$$RDF is called the $$2$$-rainbow domination number of $$G$$, denoted by $$\gamma_{2r}(G)$$. The vertex criticality index of a $$2$$-rainbow domination of a graph $$G$$ is defined as $$ci_{2r}^{v}(G)=(\sum\nolimits_{v\in V(G)}(\gamma_{2r}\left(G\right) -\gamma_{2r}\left( G-v\right)))/\left\vert V(G)\right\vert$$, the edge removal criticality index of a $$2$$-rainbow domination of a graph $$G$$ is defined as $$ci_{2r}^{-e}(G)=(\sum\nolimits_{e\in E(G)}(\gamma_{2r}\left(G\right)-\gamma_{2r}\left( G-e\right)))/\left\vert E(G)\right\vert$$ and the edge addition of a $$2$$-rainbow domination criticality index of $$G$$ is defined as $$ci_{2r}^{+e}(G)=(\sum\nolimits_{e\in E(\overline{G})}(\gamma_{2r}\left(G\right)-\gamma_{2r}\left( G+e\right)))/\left\vert E(\overline{G})\right\vert$$, where $$\overline{G}$$ is the complement graph of $$G$$. In this paper, we determine the criticality indices of paths and cycles.

Keywords: 2-rainbow domination number, criticality index.

Mathematics Subject Classification: 05C69.

Full text (pdf)

1. A. Bouchou, M. Blidia, Criticality indices of Roman domination of paths and cycles, Australasian Journal of Combinatorics 56 (2013), 103-112.
2. B. Brešar, T.K. Šumenjak, Note on the 2-rainbow domination in graphs, Discrete Applied Mathematics 155 (2007), 2394-2400.
3. B. Brešar, M.A. Henning, D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), 201-213.
4. A. Hansberg, N. Jafari Rad, L. Volkmann, Vertex and edge critical Roman domination in graphs, Utilitas Mathematica 92 (2013), 73-97.
5. J.H. Hattingh, E.J. Joubert, L.C. van der Merwe, The criticality index of total domination of path, Utilitas Mathematica 87 (2012), 285-292.
6. T.W. Haynes, C.M. Mynhardt, L.C. van der Merwe, Criticality index of total domination, Congr. Numer. 131 (1998), 67-73.
7. N. Jafari Rad, Critical concept for 2-rainbow domination in graphs, Australasian Journal of Combinatorics 51 (2011), 49-60.
8. N. Jafari Rad, L. Volkmann, Changing and unchanging the Roman domination number of a graph, Utilitas Mathematica 89 (2012), 79-95.
9. D.P. Sumner, P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983), 65-76.
10. H.B. Walikar, B.D. Acharya, Domination critical graphs, Nat. Acad. Sci. Lett. 2 (1979), 70-72.
11. Y. Wu, N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs and Combinatorics 29 (2013) 4, 1125-1133.
12. Y. Wu, H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Applied Mathematics Letters 23 (2010), 706-709.
• Ahmed Bouchou
• University of Médéa, Algeria
• Mostafa Blidia
• University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
• Communicated by Hao Li.
• Revised: 2015-02-15.
• Accepted: 2016-03-02.
• Published online: 2016-06-29.