Note on 2-rainbow domination and Roman domination in graphs

✍ Scribed by Yunjian Wu; Huaming Xing

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 244 KB
• Volume: 23
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2010.02.012

✦ Synopsis

A Roman dominating function of a graph G is a function f : V → {0, 1, 2} such that every vertex with 0 has a neighbor with 2. The minimum of f (V (G)) = v∈V f (v) over all such functions is called the Roman domination number γ R (G). A 2-rainbow dominating function of a graph G is a function g that assigns to each vertex a set of colors chosen from the set {1, 2}, for each vertex v ∈ V (G) such that g(v) = ∅, we have u∈N(v) g(u) = {1, 2}. The 2-rainbow domination number γ r2 (G) is the minimum of w(g) = v∈V |g(v)| over all such functions. We prove γ r2 (G) ≤ γ R (G) and obtain sharp lower and upper bounds for γ r2 (G) + γ r2 (G). We also show that for any connected graph G of order n ≥ 3, γ r2 (G) + γ (G) 2 ≤ n. Finally, we give a proof of the characterization of graphs with γ R (G) = γ (G) + k for 2 ≤ k ≤ γ (G).