Independent [k]-Roman Domination on Graphs

Abstract

Given a function $f:V(G)\to {\mathbb{Z}}_{\ge 0}$ on a graph $G$, $AN(v)$ denotes the set of neighbors of $v\in 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)\to \{0,1,\dots ,k+1\}$ such that ${\sum }_{u\in N[v]}f(u)\ge k+|AN(v)|$ for all $v\in V(G)$ with $f(v)<k$. The weight of $f$ is ${\sum }_{v\in V(G)}f(v)$. The $[k]$-Roman domination number, denoted by ${\gamma }_{[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)\to \{0,1,\dots ,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\ge 1$. We prove that, for all $k\ge 3$, the decision problems associated with $i_{[kR]}(G)$ and ${\gamma }_{[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ša snarks and Loupekine snarks.

19 pages