(Independent) $k$-Rainbow Domination of a Graph

Abstract

Let $G=(V,E)$ be a graph with the vertex set $V=V(G)$ and the edge set $E=E(G)$. Let $k$ be a positive integer and $\gamma_{rk}(G)$ ($\gamma_{i_{rk}}(G)$) be $k$-rainbow domination (independent $k$-rainbow domination) number of a graph $G$. In this paper, we study the $k$-rainbow domination and independent $k$-rainbow domination numbers of graphs. We obtain bounds for $\gamma_{rk}(G-e)$ ($\gamma_{i_{rk}}(G-e)$) in terms of $\gamma_{rk}(G)$ ($\gamma_{i_{rk}}(G)$). Finally, the relation between weak $3$-domination and $3$-rainbow domination number of graphs will be investigated.

Keywords

• Rainbow domination
• independent rainbow domination
• graphs

References

1. Amjadi, J., Dehgardi, N., Mohammadi, N., Sheikholeslami, S.M., Volkmann, L., \emph{Independent $2$-rainbow domination numbers in trees}, Asian-Eur. J. Math., {\bf08}(2015) 02, 1550035.
2. Bresar, B., Henning, M., Rall, D., \emph{Rainbow domination in graphs}, Taiwanese J. Math. {\bf12}(2008), 23--225.
3. Bresar, B., Sumnjak, T., \emph{On 2-rainbow domination in graphs}, Discrete Appl. Math. {\bf 155}(2007), 2394--2400.
4. Chang, G., Wu, J., Zhu, X., \emph{Rainbow domination on trees}, Discrete Appl. Math. {\bf 158}(2010), 8--12.
5. Hao, G., Mojdeh, D.A., Wei, S., Xie, Z., \emph{Rainbow domination in the Cartesian product of directed paths}, Australas. J. Combin. {\bf 70}(3)(2018), 349--361.
6. Mansouri, Z., Mojdeh, D.A., \emph{Outer independent rainbow dominating functions in graphs}, Opuscula Math. \textbf{40}(5)(2020), 599-615 https://doi.org/10.7494/OpMath.2020.40.5.599.
7. Mojdeh, D.A., Kazemi, A.P., \emph{Domination in Harary graphs}, Bulletin of the Institute of Combinatorics and its Application {\bf 49}(2007), 61--78.
8. Pai, K., Chiu, W., \emph{$3$-rainbow domination number in graphs}, In Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 713--720. Springer, Science+ Business Media Singapore, 2013.

9. West, D.B., Introduction to Graph Theory (Second Edition) (Prentice Hall, USA, 2001).
10. Wu, Y., Jafari Rad, N., \emph{Bounds on the $2$-rainbow domination number of graphs}, Graphs and Combin. {\bf 29}(2013), 1125--1133.