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.

Key words: 2-rainbow domination number, circumference, girth