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)∈e(g) or (v,w)∈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 γver(g), is known as the textit{vertex-edge roman domination number} of g. the problem of determining γ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.