Browsing by Subject "criticality index"

Now showing 1 - 1 of 1

Access status: Open Access ,
Criticality indices of 2-rainbow domination of paths and cycles
(2016) Bouchou, Ahmed; Blidia, Mostafa
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 2RDF $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.