Further results on maximal rainbow domination number

Document Type : Research Paper


Department of Mathematics, Babol Noshirvani University of Technology, Babol, I.R. Iran


‎A  2-rainbow dominating function (2RDF) of a graph $G$ is a‎ ‎function $f$ from the vertex set $V(G)$ to the set of all subsets‎ ‎of the set $\{1,2\}$ such that for any vertex $v\in V(G)$ with‎ ‎$f(v)=\emptyset$ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$‎ ‎is fulfilled‎, ‎where $N(v)$ is the open neighborhood of $v$‎. ‎A ‎ ‎maximal 2-rainbow dominating function of a graph $G$ is a ‎‎$‎‎2‎$‎-rainbow dominating function $f$ such that the set $\{w\in‎‎V(G)|f(w)=\emptyset\}$ is not a dominating set of $G$‎. ‎The‎ ‎weight of a maximal 2RDF $f$ is the value $\omega(f)=\sum_{v\in‎ ‎V}|f (v)|$‎. ‎The  maximal $2$-rainbow domination number of a‎ ‎graph $G$‎, ‎denoted by $\gamma_{m2r}(G)$‎, ‎is the minimum weight of a‎ ‎maximal 2RDF of $G$‎. ‎In this paper‎, ‎we continue the study of maximal‎ ‎2-rainbow domination {number} in graphs‎. ‎Specially‎, ‎we first characterize all graphs with large‎ ‎maximal 2-rainbow domination number‎. ‎Finally‎, ‎we determine the maximal ‎$‎2‎$‎‎-‎rainbow domination number in the sun and sunlet graphs‎.


Main Subjects

[1] H. Abdollahzadeh Ahangar, J. Amjadi, N. Jafari Rad and V. Samodivkin, Total k-rainbow domination numbers in
graphs, Commun. Comb. Optim., 3 (2018) 37–50.
[2] 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) 841–846.
[3] H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami and D. Kuziak, Maximal 2-rainbow domination number
of a graph, AKCE Int. J. Graphs Comb., 13 (2016) 157–164.
[4] H. Abdollahzadeh Ahangar, H. Jahani, N. Jafari Rad, Rainbow edge domination numbers in graphs, Asian-Eur. J.
Math., 13 (2020) (16 pages).
[5] M. Chellali and N. Jafari Rad, On 2-rainbow domination and Roman domination in graphs, Australas. J. Combin.,
56 (2013) 85–93.
[6] M. Falahat, S. M. Sheikholeslami and L. Volkmann, New bounds on the rainbow domination subdivision number,
Filomat, 28 (2014) 615–622.
[7] B. Brešar, M. A. Henning and D. F. Rall, Rainbow domiantion in graphs, Taiwanese J. Math., 12 (2008) 213–225.
[8] B. Brešar and T. Kraner Šumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math., 155 (2007)
[9] C. D. Godsil and B. D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc., 18 (1) (1978)
[10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds.), Domination in graphs: Advanced Topics, Marcel Dekker,
Inc. New York, 1998.
[11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, Inc. New
York, 1998.
[12] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin., 29 (2013)