Criticality indices of 2-rainbow domination of paths and cycles
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\)RD...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2016-01-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | http://www.opuscula.agh.edu.pl/vol36/5/art/opuscula_math_3633.pdf |
| _version_ | 1819178749848977408 |
|---|---|
| author | Ahmed Bouchou Mostafa Blidia |
| author_facet | Ahmed Bouchou Mostafa Blidia |
| author_sort | Ahmed Bouchou |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T21:47:30Z |
| format | Article |
| id | doaj.art-b2ddd249e94a4520bc92bdaf83f1ada3 |
| institution | Directory Open Access Journal |
| issn | 1232-9274 |
| language | English |
| last_indexed | 2024-12-22T21:47:30Z |
| publishDate | 2016-01-01 |
| publisher | AGH Univeristy of Science and Technology Press |
| record_format | Article |
| series | Opuscula Mathematica |
| spelling | doaj.art-b2ddd249e94a4520bc92bdaf83f1ada32022-12-21T18:11:28ZengAGH Univeristy of Science and Technology PressOpuscula Mathematica1232-92742016-01-01365563574http://dx.doi.org/10.7494/OpMath.2016.36.5.5633633Criticality indices of 2-rainbow domination of paths and cyclesAhmed Bouchou0Mostafa Blidia1University of Médéa, AlgeriaUniversity of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, AlgeriaA \(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.http://www.opuscula.agh.edu.pl/vol36/5/art/opuscula_math_3633.pdf2-rainbow domination numbercriticality index |
| spellingShingle | Ahmed Bouchou Mostafa Blidia Criticality indices of 2-rainbow domination of paths and cycles Opuscula Mathematica 2-rainbow domination number criticality index |
| title | Criticality indices of 2-rainbow domination of paths and cycles |
| title_full | Criticality indices of 2-rainbow domination of paths and cycles |
| title_fullStr | Criticality indices of 2-rainbow domination of paths and cycles |
| title_full_unstemmed | Criticality indices of 2-rainbow domination of paths and cycles |
| title_short | Criticality indices of 2-rainbow domination of paths and cycles |
| title_sort | criticality indices of 2 rainbow domination of paths and cycles |
| topic | 2-rainbow domination number criticality index |
| url | http://www.opuscula.agh.edu.pl/vol36/5/art/opuscula_math_3633.pdf |
| work_keys_str_mv | AT ahmedbouchou criticalityindicesof2rainbowdominationofpathsandcycles AT mostafablidia criticalityindicesof2rainbowdominationofpathsandcycles |