Algorithmic Aspects of Total Vertex-Edge Domination in Graphs.

A vertex v of a simple graph G = (V , E) ve-dominates every edge incident to v as well as every edge adjacent to these incident edges. A set D ⊆ V is a total vertex-edge dominating set if every edge of E is ve-dominated by a vertex of D and the subgraph induced by D has no isolated vertex. The total vertex-edge domination problem is to find a total vertex-edge dominating set of minimum cardinality. In this paper, we first show that the total vertex-edge domination problem is NP-complete for chordal graphs. Then we provide a linear-time algorithm for this problem in trees. Moreover, we show that the minimum total vertex-edge domination problem cannot be approximated within (1 −) ln | V | for any > 0 unless NP ⊆ DTIME (| V | O (log log | V |) ). Finally, we prove that the minimum total vertex-edge domination problem is APX-complete for bounded-degree graphs. [ABSTRACT FROM AUTHOR]