Vertex-edge Roman domination in graphs: Complexity and algorithms

For a simple, undirected graph G(V, E), a function h : V (G) -> {0, 1, 2} such that each edge (u, v) of G is either incident with a vertex with weight at least one or there exists a vertex w such that either (u, w) epsilon E(G) or (v, w) epsilon E(G) and h(w) = 2, is called a vertex-edge Roman dominating function (ve-RDF) of G. For a graph G, the smallest possible weight of a ve-RDF of G which is denoted by gamma veR(G), is known as the vertex-edge Roman domination number of G. The problem of determining gamma veR(G) of a graph G is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if G has a ve-RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MVERDP is presented.