Roman domination in graphs: The class ℛUV R
Vladimir Samodivkin · Discrete Mathematics Algorithms and Applications · 2016
For a graph [Formula: see text], a Roman dominating function (RDF) [Formula: see text] has the property that every vertex [Formula: see text] with [Formula: see text] has a neighbor [Formula: see text] with [Formula: see text]. The weight of a RDF [Formula: see text] is the sum [Formula: see text], and the minimum weight of a RDF on [Formula: see text] is the Roman domination number [Formula: see text] of [Formula: see text]. The Roman bondage number [Formula: see text] of [Formula: see text] is the minimum cardinality of all sets [Formula: see text] for which [Formula: see text]. A graph [Formula: see text] is in the class [Formula: see text] if the Roman domination number remains unchanged when a vertex is deleted. In this paper, we obtain tight upper bounds for [Formula: see text] and [Formula: see text] provided a graph [Formula: see text] is in [Formula: see text]. We present necessary and sufficient conditions for a tree to be in the class [Formula: see text]. We give a constructive characterization of [Formula: see text]-trees using labelings.