On [k] -Roman domination in graphs

Abstract

AbstractFor an integer [Formula: see text] let f be a function that assigns labels from the set [Formula: see text] to the vertices of a simple graph [Formula: see text]. The active neighborhood AN(v) of a vertex [Formula: see text] with respect to f is the set of all neighbors of v that are assigned non-zero values under f. A [Formula: see text]-Roman dominating function ([Formula: see text]-RDF) is a function [Formula: see text] such that for every vertex [Formula: see text] with f(v) < k, we have [Formula: see text]. The weight of a [Formula: see text]-RDF is the sum of its function values over the whole set of vertices, and the [Formula: see text]-Roman domination number [Formula: see text] is the minimum weight of a [Formula: see text]-RDF on G. In this paper we determine various bounds on the [Formula: see text]-Roman domination number. In particular, we show that for any integer [Formula: see text] every connected graph G of order [Formula: see text], satisfies [Formula: see text] and we characterize the graphs G attaining this bound. Moreover, we show that if T is a nontrivial tree, then [Formula: see text] for every integer [Formula: see text] and we characterize the trees attaining the lower bound. Finally, we prove the NP-completeness of the [Formula: see text]-Roman domination problem in bipartite and chordal graphs.

Keywords

• Roman domination
• -Roman domination
• 05C69