Independent k-Roman Domination on Graphs

Given a function f V (G) Z ₀ on a graph G, AN (v) denotes the set of neighbors of v V (G) that have positive labels under f. In 2021, Ahangar et al. ~introduced the notion of k-Roman Dominating Function (k-RDF) of a graph G, which is a function f V (G) \0, 1, , k+1\ such that ₔ ₍ₕf (u) k + |AN (v) | for all v V (G) with f (v) <k. The weight of f is ₕ ₕ (₆) f (v). The k-Roman domination number, denoted by ₊ₑ (G), is the minimum weight of a k-RDF of G. The notion of k-RDF for k=1 has been extensively investigated in the scientific literature since 2004, when introduced by Cockayne et al. as Roman Domination. An independent k-Roman dominating function (k-IRDF) f V (G) \0, 1, , k+1\ of a graph G is a k-RDF of G such that the set of vertices with positive labels is an independent set. The independent k-Roman domination number of G is the minimum weight of a k-IRDF of G and is denoted by i₊ₑ (G). In this paper, we propose the study of independent k-Roman domination on graphs for arbitrary k 1. We prove that, for all k 3, the decision problems associated with i₊ₑ (G) and ₊ₑ (G) are NP-complete for planar bipartite graphs with maximum degree 3. We also present lower and upper bounds for i₊ₑ (G). Moreover, we present lower and upper bounds for the parameter i₊ₑ (G) for two families of 3-regular graphs called generalized Blanusa snarks and Loupekine snarks.