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)\to \{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 $s{d}_{\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\ge 4$ such that $\overline{G}$ and $G$ have connected components of order at least $3$, then
$s{d}_{\gamma R}(G)+s{d}_{\gamma R}(\overline{G})\le \lfloor \frac{n}{2}\rfloor +3.$