Roman domination perfect graphs
Nader Jafari Rad, Lutz Volkmann · RWTH Publications (RWTH Aachen) · 2011
A Roman dominating function on a graph G is a function f: V (G) → {0, 1, 2} satisfying the condition that every vertex u ∈ V (G) for which f(u) = 0 is adjacent to at least one vertex v ∈ V (G) for which f(v) = 2. The weight of a Roman dominating function is the value f(V (G)) = u∈V (G) f(u). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function on G. A Roman dominating function f: V (G) → {0, 1, 2} can be represented by the ordered partition (V0, V1, V2) of V (G), where Vi = {v ∈ V (G) | f(v) = i} for i = 0, 1, 2. A Roman dominating function f = (V0, V1, V2) on a graph G is an independent Roman dominating function if V1 ∪ V2 is an independent set. The independent Roman domination number iR(G) of G is the minimum weight of an independent Roman dominating function on G. In this paper, we study graphs G for which γR(G) = iR(G). In addition, we investigate so called Roman domination perfect graphs. These are graphs G with γR(H) = iR(H) for every induced subgraph H of G. 1