Bounds for Independent Roman Domination in Graphs

摘要

A Roman dominating function on a graph G is a function f : V(G) → {0,1,2} such that every vertex u with f(u) = 0 is adjacent to a vertex v with f(v) = 2.The weight of a Roman dominating function f is the value f{V(G)) = ∑_u ∈v(G) f(u). A Roman dominating function f is an independent Roman dominating function if the set of vertices for which f assigns positive values is independent.The independent Roman domination number ir(G) of G is the minimum weight of an independent Roman dominating function of G. We show that if T is a tree of order n, then ir(T) ≤ 4n/5, and characterize the class of trees for which equality holds.We present bounds for i_R(G) in terms of the order, maximum and minimum degree, diameter and girth of G.We also present Nordhaus-Gaddum inequalities for independent Roman domination numbers.