Outer-independent total 2-rainbow dominating functions in graphs

Document Type : Original paper

Authors

1 Department of Mathematics Payame Noor University I.R. Iran

2 RWTH Aachen University

Abstract

Let G=(V,E) be a simple graph with vertex set V and edge set E. An {outer-independent total 2-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2} such that the following conditions hold: (i) for any vertex v with f(v)=∅ we have ⋃u∈NG(v)f(u)={1,2}, (ii) the set of all vertices v∈V(G) with f(v)=∅ is independent and (iii) {v∣f(v)≠∅} has no isolated vertex. The outer-independent total 2-rainbow domination number of G, denoted by γoitr2(G), is the minimum value of ω(f)=∑v∈V(G)|f(v)| over all such functions f. In this paper, we study the outer-independent total 2-rainbow domination number of G and classify all graphs with outer-independent total 2-ainbow domination number belonging to the set {2,3,n}. Among other results, we present some sharp bounds concerning the invariant.

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, 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.
[3] B. Brešar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225.
[4] B. Brešar and T.K. Šumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), no. 17, 2394–2400.
[5] G.J. Chang, J. Wu, and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010), no. 1, 8–12.
[6] 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.
[7] N. Jafari Rad and M. Krzywkowski, 2-outer-independent domination in graphs, Nat. Acad. Sci. Lett. 38 (2015), no. 3, 263–269.
[8] Q. Kang, V. Samodivkin, Z. Shao, S.M. Sheikholeslami, and M. Soroudi, Outer-independent k-rainbow domination, J. Taibah University for Science 13 (2019), no. 1, 883–891.
[9] Z. Mansouri and D.A. Mojdeh, Outer independent rainbow dominating functions in graphs, Opuscula Math. 40 (2020), no. 5, 599–615.
[10] D.B. West, Introduction to Graph Theory, Prentice-Hall of India, 1999. 
[11] W. Willis, Bounds for the independence number of a graph, Ph.D. thesis, Virginia Commonwealth University, 2011.
[12] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. 29 (2013), no. 4, 1125–1133.
 
Communications in Combinatorics and Optimization
Volume 8, Issue 2
June 2023
Pages 431-444

Files

Share

How to cite

Statistics