The k Edge-Vertex Domination Problem

Let \(G=(V(G),E(G))\) be a simple n-vertex graph with m edges. Take any \(e=uv\in E(G)\) . We say e dominates a vertex \(w\in V(G)\) provided w belongs to the closed neighborhood of u or v. Let \(S\subseteq V(G)\) , \(D\subseteq E(G)\) . Take a positive integer k. If w is edge-dominated by k edges of D, then D is called a k edge-vertex dominating set of G with respect to S. In this paper, we study the k edge-vertex domination problem and present \(O(m\lg m+k|S|+n)\) -time algorithms to find a minimum k edge-vertex dominating set of G with respect to any \(S\subseteq V(G)\) on interval graphs. In addition, we design O(n|S|)-time algorithms to find a minimum k edge-vertex dominating set of T with respect to any \(S\subseteq V(T)\) on trees.