On the Roman domination subdivision number of a graph

A Roman dominating function (RDF) of a graph G is a labeling $$f:V(G)\longrightarrow \{0,1,2\}$$f:V(G)⟶{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The weight of an RDF is the sum of its functions values over all vertices, and the Roman domination number of G is the minimum weight of an RDF of G. The Roman domination subdivision number $$\mathrm {sd}_{\gamma _{R}}(G)$$sdγR(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number of G. In this paper, we present a new upper bound on the Roman domination subdivision number by showing that for every connected graph G of order at least three, $$\begin{aligned} \mathrm {sd}_{\gamma _{R}}(G)\le 3+\min \{\deg _2(v)\mid v\in V\;\mathrm {and} \;d(v)\ge 2\}, \end{aligned}$$sdγR(G)≤3+min{deg2(v)∣v∈Vandd(v)≥2},where $$\deg _2(v)$$deg2(v) is the number of vertices of G at distance 2 from vertex v. Moreover, we show that the decision problem associated with $$\mathrm {sd}_{\gamma _{R}}(G)$$sdγR(G) is NP-hard for bipartite graphs.