独立符号双罗马控制

Independent Signed Double Roman Domination

摘要: 图$G=\left(V,E\right)$ 上的独立符号双罗马控制函数(ISDRDF)是函数$f:V\left(G\right)=\left(-1,1,2,3\right)$ ，其中：1) $f\left(v\right)=-1$ 的每个顶点$v$ 与至少两个赋值为2的顶点相邻或与至少一个赋值为3的顶点相邻；2) $f\left(v\right)=1$ 的每个顶点$v$ 与至少一个$f\left(u\right)\ge 2$ 的顶点$u$ 相邻；3) 对任意顶点$v$ ，都满足$f\left(N\left[v\right]\right)={\displaystyle {\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1}$ ；4) 所有赋值为正权重的顶点的集合是独立的。ISDRDF $f$ 的权重是$w\left(f\right)={\displaystyle {\sum }_{v\in V(G)}f\left(v\right)}$ ，且独立符号双罗马控制数$i_{sdR}\left(G\right)$ 是$G$ 中ISDRDF的最小权。本文研究了独立符号双罗马控制问题，首先给出了在$P_n$ 和$C_n$ 中的$i_{sdR}\left(G\right)$ ，然后讨论了完全图中$i_{sdR}\left(G\right)$ 的上界；最后证明了在二部图上ISDRD问题是NP-完全的。

Abstract: An independent signed double Roman dominating function (ISDRDF) on a graph $G=\left(V,E\right)$ is a function $f:V\left(G\right)\to \left\{-1,1,2,3\right\}$ such that: 1) every vertex $v$ with $f\left(v\right)=-1$ is adjacent to either at least two vertices assigned 2 or at least one vertex assigned 3; 2) every vertex $v$ with $f\left(v\right)=1$ is adjacent to at least one vertex $u$ with $f\left(u\right)\ge 2$ ; 3) for every vertex $v$ , the closed neighborhood weight satisfies$f\left(N\left[v\right]\right)={\displaystyle {\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1}$ ; and 4) the set of vertices with positive weights is independent. The weight of an ISDRDF $f$ is $w\left(f\right)={\displaystyle {\sum }_{v\in V(G)}f\left(v\right)}$ , and the independent signed double Roman domination number $i_{sdR}\left(G\right)$ is the minimum weight of an ISDRDF on $G$ . In this paper, we first determined the $i_{sdR}\left(G\right)$ for paths $P_n$ and cycles $C_n$ . Moreover, we characterize upper bound for $i_{sdR}\left(G\right)$ in complete graphs. Finally, we show that determining NP-completeness of the ISDRD problem for bipartite graphs.