2015/08/09 by Samodivkin, Vladimir
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.02089
For a graph G = (V, E), a Roman dominating function f : V → \0, 1, 2\ has the property that every vertex v ∈ 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) = ∪v∈ V f (v), and the minimum weight of a Roman dominating function on G is the Roman domination number γR(G) of G. The Roman bondage number bR(G) of G is the minimum cardinality of all sets F ⊆ E for which γR(G - F) > γR(G). A graph G is in the class RUVR if the Roman domination number remains unchanged when a vertex is deleted. In this paper we obtain tight upper bounds for γR(G) and bR(G) provided a graph G is in RUVR. We present necessary and sufficient conditions for a tree to be in the class RUV R. We give a constructive characterization of RUVR-trees using labellings.