Roman Domination Subdivision Number of a Graph and Its Complement

Abstract

A Roman dominating function of a graph \(G\) is a labeling \(f: V(G) \rightarrow \{0,1,2\}\) such that every vertex with label \(0\) has a neighbor with label \(2\). The Roman domination number \(\gamma_R(G)\) of \(G\) is the minimum of \(\sum_{v \in V(G)} f(v)\) over such functions. The Roman domination subdivision number \(sd_{\gamma 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.

In this paper, we prove that if \(G\) is a graph of order \(n \geq 4\) such that \(\overline{G}\) and \(G\) have connected components of order at least \(3\), then
\(sd_{\gamma R}(G) + sd_{\gamma R}(\overline{G}) \leq \left\lfloor \frac{n}{2} \right\rfloor + 3.\)