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