@article { author = {Kumar, Manjay and P, Venkata Subba Reddy}, title = {Vertex-edge Roman domination in graphs: complexity and algorithms}, journal = {Communications in Combinatorics and Optimization}, volume = {8}, number = {1}, pages = {23-37}, year = {2023}, publisher = {Azarbaijan Shahid Madani University}, issn = {2538-2128}, eissn = {2538-2136}, doi = {10.22049/cco.2021.27163.1206}, abstract = {For a simple, undirected graph $G(V,E)$, a function $h : V(G) \rightarrow \lbrace 0, 1, 2\rbrace$ 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) \in E(G)$ or  $(v,w) \in 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 \textit{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.}, keywords = {Vertex-edge Roman-domination,graph classes,NP-complete,Vertex cover,Integer linear programming}, url = {http://comb-opt.azaruniv.ac.ir/article_14280.html}, eprint = {http://comb-opt.azaruniv.ac.ir/article_14280_43d998ca89041cf76a7055446c9b2987.pdf} }