Abstract

{$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 $\cup_{u\in N(v)}f(u)=\{1,2\}$ is fulfilled. The {weight} of a 2RDF $f$ is the value $\omega(f)=\Sigma_{v\in V}|f (v)|$. The {$2$-rainbow domination number} of a graph $G$, denoted by $\gamma_{r2}(G)$, is the minimum weight of a 2RDF of G. The {$2$-rainbow domination subdivision number} $\tx{\rm sd}_{\gamma_{r2}}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the $2$-rainbow domination number. In this paper, we initiate the study of $2$-rainbow domination subdivision number in graphs.

Keywords: domination number; $2$-rainbow domination number; $2$-rainbow domination subdivision number.

MSC: 05C69

Pages:  102--114     

Volume  67 ,  Issue  2 ,  2015