Trees with strong equality between the Roman domination number and the unique response Roman domination number.
Nader Jafari Rad, Chun‐Hung Liu · Australas. J Comb. · 2012
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)) = ∑ u∈V (G) f(u). A function f : V (G) → {0, 1, 2} with the ordered partition (V0, V1, V2) of V (G), where Vi = {v ∈ V (G) | f(v) = i} for i = 0, 1, 2, is a unique response Roman function if x ∈ V0 implies |N(x) ∩ V2| ≤ 1 and x ∈ V1 ∪ V2 implies that |N(x) ∩ V2| = 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 uR(G)) is the minimum weight of an RDF (respectively, URRDF) on G. We say that γR(G) strongly equals uR(G), denoted by γR(G) ≡ uR(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 ) ≡ uR(T ). ∗ Also at School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran. The research was in part supported by a grant from IPM (No. 90050042). 134 NADER JAFARI RAD AND CHUN-HUNG LIU