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)=\emptyset$ we have $\bigcup_{u\in N_G(v)} f(u)=\{1,2\}$, (ii) the set of all vertices $v\in V(G)$ with $f(v)=\emptyset$ is independent and (iii) $\{v\mid f(v)\neq\emptyset\}$ has no isolated vertex. The outer-independent total $2$-rainbow domination number of $G$, denoted by ${\gamma}_{oitr2}(G)$, is the minimum value of $\omega(f)=\sum_{v\in 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