Total $k$-rainbow domination subdivision number in graphs

Abstract

A total $k$-rainbow dominating function (T$k$RDF) of $G$ is a function $f$ from the vertex set $V(G)$ to the set of all subsets of the set $\{1,\ldots,k\}$ such that (i) for any vertex $v\in V(G)$ with $f(v)=\emptyset$ the condition $\bigcup_{u \in N(v)}f(u)=\{1,\ldots,k\}$ is fulfilled, where $N(v)$ is the open neighborhood of $v$, and (ii) the subgraph of $G$ induced by $\{v \in V(G) \mid f (v) \not =\emptyset\}$ has no isolated vertex. The total $k$-rainbow domination number, $\gamma_{trk}(G)$, is the minimum weight of a T$k$RDF on $G$. The total $k$-rainbow domination subdivision number ${\rm sd}_{\gamma_{trk}}(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 total $k$-rainbow domination number. In this paper, we initiate the study of total $k$-rainbow domination subdivision number in graphs and we present sharp bounds for ${\rm sd}_{\gamma_{trk}}(G)$. In addition, we determine the total 2-rainbow domination subdivision number of complete bipartite graphs and show that the total 2-rainbow domination subdivision number can be arbitrary large.

Keywords

• total $k$-rainbow domination
• total $k$-rainbow domination subdivision number
• $k$-rainbow domination