Vertex–Edge Roman {2}-Domination

A vertex–edge Roman { 2 } -dominating function on a graph G = ( V , E ) is a function f : V ⟶ { 0 , 1 , 2 } satisfying that, for every edge u v ∈ E with f ( v ) = f ( u ) = 0 , ∑ w ∈ N ( v ) ∪ N ( u ) f ( w ) ≥ 2 . The weight of the function f is the sum ∑ a ∈ V f ( a ) . The vertex–edge Roman { 2 } -domination number of G , denoted by γ v e R 2 ( G ) , is the minimum weight of a vertex–edge Roman { 2 } -dominating function on G . In this work, we begin the study of vertex–edge Roman { 2 } -domination. We determine the exact vertex–edge Roman { 2 } -domination number for cycles and paths, and we provide a tight lower bound and a tight upper bound for the vertex–edge Roman { 2 } -domination number of trees. In addition, we prove that the decision problem associated with vertex–edge Roman { 2 } -domination is NP-complete for bipartite graphs.