On the Roman domination subdivision number of a graph (Q782761)

Let \(G\) be a graph and let \(V_0\), \(V_1\), \(V_2\) be a partition of \(V(G)\). Such a partition is a Roman partition if every vertex from \(V_0\) has a neighbor in \(V_2\). The Roman domination number is \(\gamma_R(G)=\min\{2|V_2|+|V_1|\}\), where the minimum is taken over all Roman partitions of \(G\). Further, the Roman domination subdivision number, denoted by \(\mathrm{sd}_{\gamma_R}(G)\), is the minimum number of edges of \(G\) that needs to be subdivided by one vertex, such that the Roman domination number of the new graph exceed \(\gamma_R(G)\). The present work is a two results paper. In the first the authors succeed to improve the upper bound on \(\mathrm{sd}_{\gamma_R}(G)\), that is \[\mathrm{sd}_{\gamma_R}(G)\leq 3+\min\{\mathrm{deg}_2(v):v\in V(G)\wedge {\deg}(v)\geq 2\},\] where \(\mathrm{deg}_2(v)\) represents the number of vertices at distance two to \(v\). The result on complexity follows. In particular, it is proven that the problem of determining \(\mathrm{sd}_{\gamma_R}(G)\) is NP-hard for bipartite graphs. The reduction is done from 3SAT.