New Bounds on the Rainbow Domination Subdivision Number


Mohyedin Falahat, Seyed Mahmoud Sheikholeslami, Lutz Volkmann




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\inV(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$. 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 $\text{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 prove that for every simple connected graph $G$ of order $n\geq3$, \[ \text{sd}_{\gamma_{r2}}(G)\leq3+\min\{d2(v)|v\in V \ \text{and} \ d(v)\geq2\} \] where $d_2(v)$ is the number of vertices of $G$ at distance 2 from $v$.