Lower and upper bounds on the 2-rainbow domination number of a graph

Expand
  • 1. College of Science, East China University of Technology, Nanchang 330013, Jiangxi, China
    2. School of Applied Mathematics, Xiamen University of Technology, Xiamen 361024, Fujian, China

Received date: 2021-05-24

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization

Abstract

A $2$-rainbow dominating function of a graph $G$ is a function $f$ from the vertex set $V(G) $ of $G $ to the power set of the set $\{1,2\} $ such that any vertex $v$ with $f(v)=\varnothing$ satisfies that $\bigcup_{u\in N(v)}f(u)=\{1,2\} $, where $N(v) $ is the neighborhood of $v$. The value $\sum_{v\in V(G)}|f(v)| $ is called the weight of a $2$-rainbow dominating function $f $ of $G$. The $2$-rainbow domination number of $G $ is the minimum weight of a $2$-rainbow dominating function of $G$. By the structure analysis of graphs, some new lower and upper bounds on 2-rainbow domination number of graphs are derived in terms of the number of vertices, circumference, girth and minimum degree.

Cite this article

Zhihong XIE, Guoliang HAO, Wei ZHUANG . Lower and upper bounds on the 2-rainbow domination number of a graph[J]. Operations Research Transactions, 2024 , 28(4) : 117 -122 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.011

References

1 Bre?ar B , Henning M A , Rall D F . Rainbow domination in graphs[J]. Taiwanese Journal of Mathematics, 2008, 12 (6): 213- 225.
2 Gao Z , Lei H , Wang K . Rainbow domination numbers of generalized Petersen graphs[J]. Applied Mathematics and Computation, 2020, 382, 125341.
3 Wang Y , Wu X , Dehgardi N , et al. $k$-rainbow domination number of $P_3\square P_n $[J]. Mathematics, 2019, 7 (2): 203.
4 Bre?ar B , ?umenjak T K . On the 2-rainbow domination in graphs[J]. Discrete Applied Mathematics, 2007, 155, 2394- 2400.
5 Kuzman B . On $k$-rainbow domination in regular graphs[J]. Discrete Applied Mathematics, 2020, 284, 454- 464.
6 Furuya M , Koyanagi M , Yokota M . Upper bound on $3$-rainbow domination in graphs with minimum degree 2[J]. Discrete Optimization, 2018, 29, 45- 76.
7 Abdollahzadeh Ahangar H , Amjadi J , Chellali M , et al. Total 2-rainbow domination numbers in trees[J]. Discussiones Mathematicae Graph Theory, 2021, 41 (2): 345- 364.
8 Abdollahzadeh Ahangar H , Khaibari M , Jarfari Rad N , et al. Graphs with large total 2-rainbow domination number[J]. Iranian Journal of Science and Technology Transaction A-Science, 2018, 42, 841- 846.
9 Abdollahzadeh Ahangar H , Amjadi J , Jarfarirad N , et al. Total $k$-rainbow domination numbers in graphs[J]. Communications in Combinatorics and Optimization, 2018, 3 (1): 37- 50.
10 Amjadi J , Dehgardi N , Mohammadi N , et al. Independent 2-rainbow domination in trees[J]. Asian-European Journal of Mathematics, 2015, 8 (2): 1550035.
11 Falahat M , Sheikholeslami S M , Volkmann L . New bounds on the rainbow domination subdivision number[J]. Filomat, 2014, 28 (3): 615- 622.
Outlines

/