On the outer independent 2-rainbow domination number of Cartesian products of paths and cycles

Document Type : Original paper

Author

Sirjan University of Technology, Sirjan 78137, Iran

Abstract

Let $G$ be a graph. A  $2$-rainbow dominating function (or {\em 2-RDF}) of $G$ is a function $f$ from $V(G)$ to the set of all subsets of the set $\{1,2\}$ such that for a vertex $v\in V(G)$ with $f(v)=\emptyset$, the condition $\bigcup_{u\in N_{G}(v)}f(u)=\{1,2\}$ is fulfilled, where $N_{G}(v)$ is the open neighborhood of $v$. The weight of 2-RDF $f$ of $G$ is the value $\omega (f):=\sum _{v\in V(G)}|f(v)|$. The {\em $2$-rainbow domination number} of $G$, denoted by $\gamma_{r2}(G)$, is the minimum weight of a 2-RDF of $G$. A 2-RDF $f$ is called an  outer independent $2$-rainbow dominating function (or  OI2-RDF} of $G$ if the set of all $v\in V(G)$ with $f(v)=\emptyset$ is an independent set. The outer independent $2$-rainbow domination number $\gamma_{oir2}(G)$ is the minimum weight of an OI2-RDF of $G$. In this paper, we obtain the outer independent $2$-rainbow domination number of $P_{m}\square P_{n}$ and $P_{m}\square C_{n}$. Also we determine the value of $\gamma_{oir2}(C_{m}\Box C_{n})$ when $m$ or $n$ is even. 

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, N. Jafari Rad, and V. Samodivkin, Total $k$-rainbow domination numbers in graphs, Commun. Comb. Optim. 3 (2018), no. 1, 37–50.
[2] J. Amjadi, L. Asgharsharghi, N. Dehgardi, M. Furuya, S.M. Sheikholeslami, and L. Volkmann, The $k$-rainbow reinforcement numbers in graphs, Discrete Appl. Math. 217 (2017), 394–404.
[3] J. Amjadi, N. Dehgardi, M. Furuya, and S.M. Sheikholeslami, A sufficient condition for large rainbow domination number, Int. J. Comput. Math. Comput. Syst. Theory 2 (2017), no. 2, 53–65.
[4] J. Amjadi, R. Khoeilar, N. Dehgardi, S.M. Sheikholeslami, and L. Volkmann, The restrained rainbow bondage number of a graph, Tamkang J. Math. 49 (2018), no. 2, 115–127.
[5] B. Brešar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225.
[6] B. Brešar and T.K. Šumenjak,  On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), no. 17, 2394–2400.
[7] G.J. Chang, J. Wu, and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010), no. 1, 8–12.
[8] N. Dehgardi, M. Falahat, S.M. Sheikholeslami, and A. Khodkar, On the rainbow domination subdivision numbers in graphs, Asian-Eur. J. Math. 9 (2016), no. 1, ID: 1650018.
[9] N. Dehgardi, S.M. Sheikholeslami, and L. Volkmann, The k-rainbow bondage number of a graph, Discrete Appl. Math. 174 (2014), 133–139.
[10] N. Dehgardi, S.M. Sheikholeslami, and L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), no. 2, 102–114.
[11] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[12] Q. Kang, V. Samodivkin, Z. Shao, S.M. Sheikholeslami, and M. Soroudi, Outerindependent k-rainbow domination, Journal of Taibah University for Science 13 (2019), no. 1, 883–891.
[13] D. Meierling, S.M. Sheikholeslami, and L. Volkmann, Nordhaus–Gaddum bounds on the $k$-rainbow domatic number of a graph, Appl. Math. lett. 24 (2011), no. 10, 1758–1761.
[14] Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlič, and J. Žerovnik,  On rainbow domination numbers of graphs, Inform. Sci. 254 (2014), 225–234.
[15] S.M. Sheikholeslami and L. Volkmann, The $k$-rainbow domatic number of a graph, Discuss. Math. Graph Theory 32 (2012), no. 1, 129–140.
[16] C. Tong, X. Lin, Y. Yang, and M. Luo, 2-rainbow domination of generalized petersen graphs $P(n, 2)$, Discrete Appl. Math. 157 (2009), no. 8, 1932–1937.
[17] Y. Wang, X. Wu, N. Dehgardi, J. Amjadi, R. Khoeilar, and J.-B. Liu, $k$-rainbow domination number of $P_3×P_n$, Mathematics 7 (2019), no. 2, ID: 203.
[18] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. 29 (2013), no. 4, 1125–1133.
[19] G. Xu, 2-rainbow domination in generalized Petersen graphs $P(n, 3)$, Discrete Appl. Math. 157 (2009), no. 11, 2570–2573.
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 315-324

Files

Share

How to cite

Statistics