Roman domination in unicyclic graphs
P. Roushini Leely Pushpam, T. N. M. Malini Mai · Journal of Discrete Mathematical Sciences and Cryptography · 2012
A Roman dominating function 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 a Roman dominating function is the value w (f) = ∑ u∈V f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G denoted by γ R (G). It has been observed that γ (G) ≤ γ R (G) ≤ 2γ (G), where γ(G) is the domination number of G. In this paper, we characterize all connected unicyclic graphs for which γ R (G) ≤ γ(G) + 2.