The edge-vertex domination and weighted edge-vertex domination problem

Consider a simple (edge weighted) graph $$G = \left( {V,E} \right)$$ G = V , E with $$\left| V \right| = n$$ V = n and $$\left| E \right| = m$$ E = m . Let $$xy \in E$$ x y ∈ E . The domination of a vertex $$z \in V$$ z ∈ V by an edge $$xy$$ xy is defined as $$z$$ z belonging to the closed neighborhood of either $$x$$ x or $$y$$ y . An edge set $$W$$ W is considered as an edge-vertex dominating set of $$G$$ G if each vertex of $$V$$ V is dominated by some edge of $$W$$ W . The (weighted) edge-vertex domination problem aims to find an edge-vertex dominating set of $$G$$ G with the minimum cardinality. Let $$M \subseteq V$$ M ⊆ V and $$N \subseteq E$$ N ⊆ E . Given a positive integer $$p$$ p , if a vertex $$z$$ z is dominated by $$p$$ p edges in set $$N$$ N , then set $$N$$ N is called a $$p$$ p edge-vertex dominating set of graph $$G$$ G with respect to $$M$$ M . This study investigates the edge-vertex domination problem and the $$p$$ p edge-vertex domination problem, presents an algorithm with a time complexity of $$O\left( {nm^{2} } \right)$$ O n m 2 for solving the weighted edge-vertex domination problem on unit interval graphs. Moreover, algorithms have been developed with time complexities of $$O\left( {m\lg m + p\left| M \right| + n} \right)$$ O m lg m + p M + n and $$O\left( {n\left| M \right|} \right)$$ O n M for identifying a minimum $$p$$ p edge-vertex dominating set of an interval graph $$G$$ G and a tree $$T$$ T , respectively, with respect to any subset $$M \subseteq V$$ M ⊆ V .