Properties and computational complexity of k-Isolate domination in graphs

Abstract

 A dominating set $S$ of a graph $G$ is said to be an isolate dominating set of $G$ if the induced subgraph $\langle S \rangle$ has at least one isolated vertex $\cite{sahul}$. A dominating set $D$ of $G$ is said to be an unique isolate dominating set(UIDS) of $G$ if $\langle D\rangle$ has exactly one isolated vertex $\cite{nirmala}$. A dominating set $D$ of $G$ is said to be a $k$-isolate dominating set(kIDS) of $G$ if $\langle D\rangle$ has exactly $k$ isolated vertices. The minimum and maximum cardinality of a minimal $k$-isolate dominating set of $G$ are called the $k$-isolate domination number $\gamma_{k,0}(G)$ and the  $k$-isolate upper domination number $\Gamma_{k,0}(G)$ respectively.\\ In this paper we have discussed some basic properties of kIDS and also we study the decision problem for $k$ID is NP-complete.