Opuscula Math. 36, no. 5 (), 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

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.