## 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)) = ∑ _{u∈V (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).

Original language | English (US) |
---|---|

Pages (from-to) | 133-140 |

Number of pages | 8 |

Journal | Australasian Journal of Combinatorics |

Volume | 54 |

Issue number | 2 |

State | Published - 2012 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics