Roman domination in graphs: the class $\mathcal{R}_\mathbf{UV R}$

Vladimir Samodivkin

Published 2015-08-09Version 1

For a graph $G = (V, E)$, a Roman dominating function $f : V \rightarrow \{0, 1, 2\}$ has the property that every vertex $v \in V $with $f (v) = 0$ has a neighbor $u$ with $f (u) = 2$. The weight of a Roman dominating function $f$ is the sum $f (V) = \cup_{v\in V} f (v)$, and the minimum weight of a Roman dominating function on $G$ is the Roman domination number $\gamma_R(G)$ of $G$. The Roman bondage number $b_R(G)$ of $G$ is the minimum cardinality of all sets $F \subseteq E$ for which $\gamma_R(G - F) > \gamma_R(G)$. A graph $G$ is in the class $\mathcal{R}_{UVR}$ if the Roman domination number remains unchanged when a vertex is deleted. In this paper we obtain tight upper bounds for $\gamma_R(G)$ and $b_R(G)$ provided a graph $G$ is in $\mathcal{R}_{UVR}$. We present necessary and sufficient conditions for a tree to be in the class $\mathcal{R}_{UV R}$. We give a constructive characterization of $\mathcal{R}_{UVR}$-trees using labellings.