Trees with strong equality between the Roman domination number and the unique response Roman domination number
Academic Article
Overview
Additional Document Info
View All
Overview
abstract
A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = uV (G) f(u). A function f: V (G) {0, 1, 2} with the ordered partition (V 0, V 1, V 2) of V (G), where V i = { V (G) {pipe} f() = i} for i = 0, 1, 2, is a unique response Roman function if x V 0 implies {pipe}N(x) V 2{pipe} 1 and x V 1 V 2 implies that {pipe}N(x) V 2{pipe} = 0. A function f: V (G) {0, 1, 2} is a unique response Roman dominating function (or just URRDF) if it is a unique response Roman function and a Roman dominating function. The Roman domination number R(G) (respectively, the unique response Roman domination number u R(G)) is the minimum weight of an RDF (respectively, URRDF) on G. We say that R(G) strongly equals u R(G), denoted by R(G) u R(G), if every RDF on G of minimum weight is a URRDF. In this paper we provide a constructive characterization of trees T with R(T) u R(T).
