Outer independent signed double Roman domination

Abstract

Suppose $[3]=\{0,1,2,3\}$ and $[3^{-}]=\{-1,1,2,3\}$. An outer independent signed double Roman dominating function (OISDRDF) of a graph $\Gamma$ is function $l:V({\Gamma })\rightarrow [3^{-}]$ for which (i) each vertex t with $l(t)=-1$ is joined to at least two vertices labeled a 2 or to at least one vertex z with $l(z)=3$, (ii) each vertex t with $l(t)=1$ is joined to at least a vertex z with $l(z)\ge 2,$ (iii) $l(N[t])=\sum _{w\in N[t]}l(w)\ge 1$ occurs for each vertex t, (iv) the set of vertices labeled $-1$ under l is an independent set. The weight of an OISDRDF is the sum of its function values over all vertices, and the outer independent signed double Roman domination number (OISDRD-number) $\gamma _{sdR}^{oi}(\Gamma )$ is the minimum weight of an OISDRDF on $\Gamma$. We first show that determining the number $\gamma _{sdR}^{oi}(\Gamma )$ is NP-complete for bipartite and chordal graphs. Then we provide exact values of this parameter for paths and cycles. Moreover, we show that for trees T of order $n\ge 3,$ $\gamma _{sdR}^{oi}(\Gamma )\le n-1,$ and we characterize extremal trees attaining this bound.