On k-Vertex-Edge Domination of Graph

Let \(G=(V,E)\) $G=(V,E)$ be a simple undirected graph. The open neighbourhood of a vertex v in G is defined as \(N_G(v)=\{u\in V~|~ uv\in E\}\) $N_G(v)=\{u\in V|uv\in E\}$ , whereas the closed neighbourhood is defined as \(N_G[v]= N_G(v)\cup \{v\}\) $N_G[v]=N_G(v)\cup \{v\}$ . For an integer k, a subset \(D\subseteq V\) $D\subseteq V$ is called a k-vertex-edge dominating set of G if for every edge \(uv\in E\) $uv\in E$ , \(|(N_G[u]\cup N_G[v]) \cap D|\ge k\) $|(N_G[u]\cup N_G[v])\cap D|\ge k$ . In k-vertex-edge domination problem, our goal is to find a k-vertex-edge dominating set of minimum cardinality of an input graph G. In this paper, we first prove that the decision version of k-vertex-edge domination problem is NP-complete for chordal graphs. On the positive side, we design a linear time algorithm for finding a minimum k-vertex-edge dominating set of tree. We also prove that there is a \(O(\log (\Delta (G)))\) $O(log(\mathrm{\Delta }(G)))$ -approximation algorithm for this problem in general graph G, where \(\Delta (G)\) $\mathrm{\Delta }(G)$ is the maximum degree of G. Then, we show that for a graph G with n vertices, this problem cannot be approximated within a factor of \((1-\epsilon ) \ln n\) $(1-ϵ)lnn$ for any \(\epsilon >0\) $ϵ>0$ unless \(NP\subseteq {\textrm{DTIME}}(|V|^{O(\log \log |V|)})\) $NP\subseteq \text{DTIME}(|V{|}^{O(loglog|V|)})$ . Finally, we prove that it is APX-complete for graphs with bounded degree \(k+3\) $k+3$ .