The vertex-edge locating Roman domination of some graphs

Abstract

In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating \({(ve-LRD)}\) function of a graph \(G=(V,E)\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that the following conditions are satisfied: (i) for every adjacent vertices \(u,v\) with \(f(u)=0\) or \(f(v)=0\), there exists a vertex \(w\) at distance \(1\) or \(2\) from \(u\) or \(v\) with \(f(w)=2\), (ii) for every edge \(uv\in E\), \(\max[f(u),f(v)]\neq 0\), and (iii) any pair of distinct vertices \(u,v\) with \(f(u)=f(v)=0\) does not have a common neighbour \(w\) with \(f(w)=2\). The weight of ve-LRD function is the sum of its function values over all the vertices. The vertex-edge locating Roman domination number of \(G\), denoted by \(\gamma_{veLR}(G)\), is the minimum weight of a {ve-LRD} function in \(G\). We proved that the vertex-edge locating Roman domination problem is NP-complete for bipartite graphs. Also, we present the upper and lower bounds of \({ve-LRD}\) function for trees. Lastly, we give the upper bounds of \({ve-LRD}\) function for some connected graphs.