On $k$-rainbow independent domination in graphs

Abstract

In this paper, we define a new domination invariant on a graph $G$, which coincides with the ordinary independent domination number of the generalized prism $G\square K_k$, called the $k$-rainbow independent domination number and denoted by ${\gamma }_{\mathrm{ri}k}(G)$. Some bounds and exact values concerning this domination concept are determined. As a main result, we prove a Nordhaus-Gaddum-type theorem on the sum for $2$-rainbow independent domination number, and show if G is a graph of order $n\ge 3$, then $5\le {\gamma }_{\mathrm{ri}2}(G)+{\gamma }_{\mathrm{ri}2}(\overline{G})\le n+3$, with both bounds being sharp.

16 pages, 2 figures, 18 references