Complexity results for $k$-domination and $\alpha$-domination problems and their variants

Abstract

Let $G=(V,E)$ be a simple and undirected graph. For some integer $k\ge 1$, a set $D\subseteq V$ is said to be a k-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $k$ neighbors in $D$. Furthermore, for some real number $\alpha$ with $0<\alpha \le 1$, a set $D\subseteq V$ is called an $\alpha$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $\alpha \times d_v$ neighbors in $D$, where $d_v$ is the degree of $v$ in $G$. The cardinality of a minimum $k$-dominating set and a minimum $\alpha$-dominating set in $G$ is said to be the $k$-domination number and the $\alpha$-domination number of $G$, respectively. In this paper, we present some approximability and inapproximability results on the problem of finding $k$-domination number and $\alpha$-domination number of some classes of graphs. Moreover, we introduce a generalization of $\alpha$-dominating set which we call an $f$-dominating set. Given a function $f:\mathbb{N}\to \mathbb{R}$, where $\mathbb{N}=\{1,2,3,\dots \}$, a set $D\subseteq V$ is said to be an $f$-dominating set in $G$ if every vertex $v$ of $G$ outside $D$ has at least $f(d_v)$ neighbors in $D$. We prove NP-hardness of the problem of finding a minimum $f$-dominating set in $G$, for a large family of functions $f$.