k−strong k−weak domination in graphs and semigraphs

Abstract

Let $G=(V,E)$ be a graph, $k$ is a positive integer and let $S=(U,X)$ be a semigraph. A subset $D\subseteq V$ is called a $k-$strong(weak) dominating set of the graph $G$ if every vertex $v\in V-D$ is strongly(weakly) dominated by at least $k$ vertices of $D$. The $k-$strong(weak)domination number $\gamma_k^s ~(\gamma_k^w)$ is the minimum cardinality of $k-$strong(weak) dominating set of $G$. A subset $D \subseteq U$ is called $k-$ strong(weak) adjacent dominating set of semigraph $S$ if every vertex $u\in U-D$ is strongly(weakly) adjacent dominated by at least $k$ vertices of $D$. The minimum cardinality of a $k-$ strong adjacent dominating set, a $k-$ weak adjacent dominating set are respectively denoted as $\gamma_k^{s,a}(S)$ and $\gamma_k^{w,a}(S)$. In this paper, we determine $\gamma_k^s $ and $\gamma_k^w $ for standard graphs. Also, we establish bounds on the above domination parameters for graphs and semigraphs. We prove that the $k-$strong(weak) domination problem is NP-complete for general graphs.