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)=∅ we have ⋃u∈N(v)g(u)={1,2}. The weight of a 2-rainbow dominating function g is the value w(g)=∑v∈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 γr2(G) (respectively, the independent 2-rainbow domination number ir2(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≥3, with ℓ leaves and s support vertices, ir2(T)≤(14n+ℓ+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