A new upper bound on the independent $2$-rainbow domination number in trees

Document Type : Original paper

Authors

1 Shahed University

2 Islamic Azad University

3 ‎Islamic Azad University

4 Islamic Azad University,

Abstract

A $2$-rainbow dominating function on a graph $G$ is a function $g$ that assigns to each vertex a set of colors chosen from the subsets of $\{1, 2\}$ so that for each vertex with $g(v) =\emptyset$ we have $\bigcup_{u\in N(v)} g(u) = \{1, 2\}$. The weight of a $2$-rainbow dominating function $g$ is the value $w(g) = \sum_{v\in V(G)} |f(v)|$. A $2$-rainbow dominating function $g$ is an independent $2$-rainbow dominating function if no pair of vertices assigned nonempty sets are adjacent. The $2$-rainbow domination number $\gamma_{r2}(G)$ (respectively, the independent $2$-rainbow domination number $i_{r2}(G)$) is the minimum weight of a $2$-rainbow dominating function (respectively, independent $2$-rainbow dominating function) on $G$. We prove that for any tree $T$ of order $n\geq 3$, with $\ell$ leaves and $s$ support vertices, $i_{r2}(T)\leq (14n+\ell+s)/20$, thus improving the bound given in [Independent 2-rainbow domination in trees, Asian-Eur. J. Math. 8 (2015) 1550035] under certain conditions.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Total 2-rainbow domination numbers of trees, Discuss. Math. Graph Theory 41 (2021), no. 2, 345–360.
[2] 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.
[3] H. Abdollahzadeh Ahangar, M. Khaibari, N. Jafari Rad, and S.M. Sheikholeslami, Graphs with large total 2-rainbow domination number, Iran. J. Sci. Technol. Trans. A Sci. 42 (2018), no. 2, 841–846.
[4] J. Amjadi, M. Chellali, M. Falahat, and S.M. Sheikholeslami, Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers, Trans. Comb. 4 (2015), no. 2, 1–11.
[5] J. Amjadi, N. Dehgardi, N. Mohammadi, S.M. Sheikholeslami, and L. Volkmann, Independent 2-rainbow domination in trees, Asian-Eur. J. Math. 8 (2015), no. 2, Article ID: 1550035.
[6] J. Amjadi, M. Falahat, S.M. Sheikholeslami, and N. Jafari Rad, Strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers in trees, Bull. Malays. Math. Sci. Soc. 39 (2016), no. 1, 205–218.
[7] B. Brešar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225.
[8] B. Brešar and T.K. Šumenjak,  On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), no. 17, 2394–2400.
[9] S. Brezovnik and T.K. Šumenjak, Complexity of $k$-rainbow independent domination and some results on the lexicographic product of graphs, Applied Math. Comput. 349 (2019), 214–220.
[10] M. Chellali and N. Jafari Rad, Independent 2-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 (2015), 133–148.
[11] N. Dehgardi, On the outer independent 2-rainbow domination number of Cartesian products of paths and cycles, Commun. Comb. Optim. 6 (2021), no. 2, 315–324.
[12] T.W. Haynes, S. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
[13] Z. Shao, Z. Li, A. Peperko, J. Wan, and J. Žerovnik, Independent rainbow domination of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019), no. 2, 417–435.
[14] T.K. Šumenjak, D.F. Rall, and A. Tepeh, On $k$-rainbow independent domination in graphs, Applied Math. Comput. 333 (2018), 353–361.
 
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 261-270

Files

Share

How to cite

Statistics