Total vertex-edge domination in graphs: Complexity and algorithms.

Let G = (V , E) be a simple, undirected and connected graph. A vertex v of a simple, undirected graph v e -dominates all edges incident to at least one vertex in its closed neighborhood N [ v ]. A set D of vertices is a vertex-edge dominating set of G , if every edge of graph G is v e -dominated by some vertex of D. A vertex-edge dominating set D of G is called a total vertex-edge dominating set if the induced subgraph G [ D ] has no isolated vertices. The total vertex-edge domination number γ ve t (G) is the minimum cardinality of a total vertex-edge dominating set of G. In this paper, we prove that the decision problem corresponding to γ ve t (G) is NP-complete for chordal graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. The problem of determining γ ve t (G) of a graph G is called the minimum total vertex-edge domination problem (MTVEDP). We prove that MTVEDP is linear time solvable for chain graphs and threshold graphs. We also show that MTVEDP can be approximated within approximation ratio of ln (Δ − 0. 5) + 1. 5. It is shown that the domination and total vertex-edge domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MTVEDP is presented. [ABSTRACT FROM AUTHOR]