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

Abstract

For a graph $G=(V,E)$, a Roman dominating function $f:V\to \{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}}_{UVR}$. We give a constructive characterization of ${\mathcal{R}}_{UVR}$-trees using labellings.

arXiv comment19 pages, 3 figures

References in corpus (1)

• On the Roman Bondage Number of Graphs on surfaces