The Nk-valued Roman Domination and Its Boundaries

The Roman dominating function on a graph G=(V,E) is a labeling f:V→{0,1,2} satisfying that any vertex v with f(v)=0 is adjacent to a vertex u with f(u)=2. In this paper, we generalize the notion of independence and dominance between two vertices. This gives a new generalization of Roman domination, called Nk-valued Roman domination, where the codomain of the Roman dominating function is extended to Nk={0,1,2,…,k}. Two lower bounds of this Nk-valued Roman domination number in terms of the diameter and radius of G respectively are established.