Vertex-Edge Roman Domination

H. Naresh Kumar, Y. B. Venkatakrishnan

A vertex-edge Roman dominating function (or just ve-RDF) of a graph $G=(V,E)$ is a function $f:V(G)\rightarrow \{0,1,2\}$ such that for each edge $e=uv$ either $\max \{f(u),f(v)\}\neq 0$ or there exists a vertex $w$ such that either $wu\in E$ or $wv\in E$ and $f(w)=2$. The weight of a ve-RDF is the sum of its function values over all vertices. The vertex-edge Roman domination number of a graph $G$, denoted by $\gamma _{veR}(G)$, is the minimum weight of a ve-RDF $G$. In this paper, we initiate a study of vertex-edge Roman dominaton. We first show that determining the number $\gamma _{veR}(G)$ is NP-complete even for bipartite graphs. Then we show that if $T$ is a tree different from a star with order $n$, $l$ leaves and $s $ support vertices, then $\gamma _{veR}(T)\geq (n-l-s+3)/2$, and we characterize the trees attaining this lower bound. Finally, we provide a characterization of all trees with $\gamma _{veR}(T)=2\gamma ^{\prime }(T)$, where $\gamma ^{\prime }(T)$ is the edge domination number of $T$.