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 { deg 2 ( v ) ∣ v ∈ V and d ( v ) ≥ 2 } , where $$\deg _2(v)$$ deg 2 ( 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.