Independent [k]-Roman Domination on Graphs

Given a function f V(G) → Z≥ 0 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 ∑u ∈ N[v]f(u) ≥ k + |AN(v)| for all v ∈ V(G) with $f(v)<k$. The weight of f is ∑v ∈ V(G)f(v). The $[k]$-Roman domination number, denoted by γ[kR](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[kR](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[kR](G) and γ[kR](G) are NP-complete for planar bipartite graphs with maximum degree 3. We also present lower and upper bounds for i[kR](G). Moreover, we present lower and upper bounds for the parameter i[kR](G) for two families of 3-regular graphs called generalized Blanu{s}a snarks and Loupekine snarks.