独立符号双罗马控制

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.

1. 引言

2004年，Cockayne等人[1]定义了图$G=\left(V,E\right)$ 上的罗马控制函数(RDF)为函数$f:V\to \left\{0,1,2\right\}$ ，满足：$f\left(u\right)=0$ 的每个顶点$u$ 都与至少一个$f\left(v\right)=2$ 的顶点$v$ 相邻。如果集合$\left\{u\in V\left(G\right)|f\left(u\right)\ge 1\right\}$ 是独立集，则罗马控制函数$f:V\left(G\right)\to \left\{0,1,2\right\}$ 称为独立罗马控制函数(IRDF)，独立罗马控制数$i_R\left(G\right)$ 是IRDF在$G$ 上的最小权。

2016年，Beeler等人[2]提出了图的双罗马控制的概念。图$G$ 上的一个双罗马控制函数(DRDF)是一个函数$f:V\to \left\{0,1,2,3\right\}$ ，它具有如下性质：如果$f\left(v\right)=0$ ，则顶点$v$ 在$f$ 下至少有两个赋值为2的邻居或一个赋值为3的邻居；如果$f\left(v\right)=1$ ，则顶点$v$ 至少有一个邻居$w$ ，其中$f\left(w\right)\ge 2$ 。图$G$ 的双罗马控制数${\gamma }_{dR}\left(G\right)$ 是图$G$ 上的一个DRDF的最小权。双罗马控制这一模型在应急服务部署、网络安全、军事防御等领域具有广泛的实际应用[3]。

2020年，Maimani等人[4]在双罗马控制的基础上提出了独立双罗马控制。如果集合$\left\{u\in V\left(G\right)|f\left(u\right)\ge 1\right\}$ 是独立集，则$\text{DRDF }f=\left(V_0,V_1,V_2,V_3\right)$ 称为独立双罗马控制函数(IDRDF)。独立双罗马控制数$i_{dR}\left(G\right)$ 是$G$ 上IDRDF的最小权，具有权$i_{dR}\left(G\right)$ 的$G$ 的IDRDF称为$G$ 的$i_{dR}$ -函数或$i_{dR}\left(G\right)$ -函数。

2018年，Ahangar等人[5]定义了图$G=\left(V,E\right)$ 上的符号双罗马控制函数(SDRDF)是一个函数$f:V\left(G\right)\to \left\{-1,1,2,3\right\}$ ，使得：1) $f\left(v\right)=-1$ 的每个顶点$v$ 与至少两个赋值为2的顶点相邻或与至少一个赋值为3的顶点相邻；2) $f\left(v\right)=1$ 的每个顶点$v$ 与至少一个$f\left(w\right)\ge 2$ 的顶点$w$ 相邻；3) $f\left(N\left[v\right]\right)={\displaystyle {\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1}$ ，对任意顶点$v$ 成立。符号双罗马控制数${\gamma }_{sdR}\left(G\right)$ 是$G$ 上SDRDF的最小权，因此具有最小权的SDRDF称为${\gamma }_{sdR}\left(G\right)$ -函数。

据我们目前所知，不同图类(二分图、弦图、区间图、块图、树)在控制、符号控制、罗马控制、双罗马控制、独立双罗马控制、符号双罗马控制中的研究情况如表1所示。值得注意的是，符号控制，独立双罗马控制问题和符号双罗马控制在区间图、块图和树中的研究仍待探索。这些开放问题可结合图的结构特性探索动态规划或分治策略，其解决将深化对控制问题的理论理解，并为复杂图类的应用奠定基础。

Table 1. Algorithmic complexity of domination variants in special graphs

表1. 在特殊图中控制变体的算法复杂性

图类	控制	符号控制	罗马控制	双罗马控制	独立双罗马控制	符号双罗马控制
二分图	$NP-C$ [6]	$NP-C$ [10]	$NP-C$ [11]	$NP-C$ [14]	$NP-C$ [18]	$NP-C$ [19]
弦图	$NP-C$ [7]	$NP-C$ [10]	open	$NP-C$ [14]	$NP-C$ [18]	$NP-C$ [19]
区间图	$O\left(n+m\right)$ [8]	open	$O\left(n\right)$ [12]	$O\left(n+m\right)$ [15]	open	open
块图	$O\left(n+m\right)$ [9]	open	$O\left(n+m\right)$ [13]	$O\left(n+m\right)$ [16]	open	open
树	$O\left(n+m\right)$ [9]	open	$O\left(n+m\right)$ [1]	$O\left(n+m\right)$ [17]	open	open

设$f:V\left(G\right)\to \left\{x_1,x_2,\cdots ,x_k\right\}$ 是一个函数，令$V_{x_i}=\left\{v\in V\left(G\right):f\left(v\right)=x_i\right\}$ ，记$f=\left(V_{x_1},V_{x_2},\cdots ,V_{x_k}\right)$ (或$f=\left(V_{x_1}^f,V_{x_2}^f,\cdots ,V_{x_k}^f\right)$ )。

在上述工作的启发下，我们研究了一类新的控制函数——独立符号双罗马控制函数，缩写为ISDRDF。

一个图$G=\left(V,E\right)$ 上的独立符号双罗马控制函数(ISDRDF)为满足以下条件的控制函数$f:V\left(G\right)\to \left\{-1,1,2,3\right\}$ ，其中：1) $f\left(v\right)=-1$ 的每个顶点$v$ 与至少两个赋值为2的顶点相邻或与至少一个赋值为3的顶点相邻；2) $f\left(v\right)=1$ 的每个顶点$v$ 与至少一个赋值不小于2的顶点相邻；3) $f\left[v\right]=f\left(N\left[v\right]\right)={\displaystyle {\sum }_{u\in N\left[v\right]}f\left(u\right)}\ge 1$ ，对任意顶点$v$ 成立；4) 集合$\left\{u\in V\left(G\right)\}f\left(u\right)\ge 1\right\}$ 是独立集。$\text{ISDRDF }f$ 的权重是值$f\left(V\left(G\right)\right)={\displaystyle {\sum }_{v\in V(G)}f\left(v\right)}$ ，且独立符号双罗马控制数$i_{sdR}\left(G\right)$ 是$G$ 中ISDRDF的最小权，因此权重为$i_{sdR}\left(G\right)$ 的ISDRDF称为$i_{sdR}\left(G\right)$ -函数。

2. 基础知识

一般地，下文中使用文献[20]中的记号和图论术语。令$G=\left(V,E\right)$ 是一个边集为$E$ ，顶点集为$V$ 且阶数为$n$ 的图。顶点$v$ 的开邻域记为$N\left(v\right)=\left\{u\in V|uv\in E\right\}$ ，闭邻域记为$N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$ 。用$P_n$ 表示$n$ 阶的路径，用$C_n$ 表示$n$ 阶的圈，用$K_n$ 表示$n$ 阶的完全图。设$V^{\prime }\subseteq V\left(G\right)$ ，以$G$ 中两端点都在$V^{\prime }$ 为顶点集，以$V^{\prime }$ 中的边的全体为边集所组成的子图，称为图$G$ 由顶点集$V^{\prime }$ 导出的子图，简称为图$G$ 的点导出子图，记为$G\left[V^{\prime }\right]$ 。如果$D$ 中没有两个顶点由边连接，则集合$D\subseteq V$ 是独立的。控制数$\gamma \left(G\right)$ 等于图中控制集的最小基数。对于一个实数$x$ ，将不大于$x$ 的最大整数写成$\lfloor x\rfloor$ ，将不小于$x$ 的最小整数写成$\lceil x\rceil$ ，有：$\lfloor x\rfloor \le x\le \lceil x\rceil$ 。为了方便读者理解数学符号，表2总结了本文出现的重要数学符号，以供查阅。

Table 2. Overview table of important mathematical symbols

表2. 重要数学符号总览表

符号	解释说明
SDRDF	符号双罗马控制函数
${\gamma }_{sdR}\left(G\right)$	图$G$ 的符号双罗马控制数
ISDRDF	独立符号双罗马控制函数
$i_{sdR}\left(G\right)$	图$G$ 的独立符号双罗马控制数
$\text{ISDRDF }f$	独立符号双罗马控制函数$f$
ISDRD	独立符号双罗马控制

3. 主要结果

3.1. 一般图结果

结论1：对任意图$G$ ，有$i_{sdR}\left(G\right)\ge {\gamma }_{sdR}\left(G\right)$ 。

证明：由于$G$ 上任意一个ISDRDF均满足SDRDF的定义，所以$G$ 上任意一个ISDRDF也是一个SDRDF。又由于任意一个ISDRDF中所有赋值为正权重的顶点的集合是独立的，则一定有$i_{sdR}\left(G\right)\ge {\gamma }_{sdR}\left(G\right)$ 。 □

结论2：对于任意图$G$ ，都有一个$i_{sdR}\left(G\right)$ -函数$f=\left(V_{-1},V_1,V_2,V_3\right)$ ，可使得$V_1=\varnothing$ 。

证明：设$h=\left(V_{-1},V_1,V_2,V_3\right)$ 是一个使得$\left|V_1\right|$ 尽可能小的$i_{sdR}\left(G\right)$ -函数。如果$V_1\ne \varnothing$ ，则至少存在一个$v\in V_1$ ，且$v$ 在$V_2\cup V_3$ 中有一个邻居$u$ 。然而由$f\left(v\right)=-1$ ，$f\left(u\right)=3$ 和$f\left(x\right)=h\left(x\right)$ 定义的函数$f=\left(V_{-1}\cup \left\{v\right\},V_1\backslash \left\{v\right\},V_2\backslash \left\{u\right\},V_3\cup \left\{u\right\}\right)$ 也是一个$i_{sdR}\left(G\right)$ -函数，使得$\left|V_1^f\right|<\left|V_1^h\right|$ ，这与$h$ 的选择是矛盾的。故$V_1=\varnothing$ 。 □

3.2. 路径与圈结果

在探讨了一般图中独立符号双罗马控制函数的基本性质后，我们将研究路径$P_n$ 与圈$C_n$ 的独立符号双罗马控制数，这对于深入理解该函数在特殊图类中的特性有关键意义。

引理3 [21]：设$G$ 为$P_n$ ，对于$n\ge 2$ ，${\gamma }_{sdR}\left(P_n\right)=\{\begin{array}{l}\frac{n}{3} ,若n\equiv 0\left(\mathrm{mod}3\right),\hfill \\ \lceil \frac{n}{3}\rceil +1,若n\equiv 1,2\left(\mathrm{mod}3\right)。\hfill \end{array}$

推论4：设$G$ 为$P_n$ ，对于$n\ge 2$ ，$i_{sdR}\left(P_n\right)={\gamma }_{sdR}\left(P_n\right)$ 。

证明：先证$i_{sdR}\left(P_n\right)\le {\gamma }_{sdR}\left(P_n\right)$ 。设$P_n=v_1{v}_2\cdots v_n$ ，定义$f:V\left(P_n\right)\to \left\{-1,1,2,3\right\}$ 满足如下条件：若$n\equiv 0\left(\mathrm{mod}3\right)$ ，则令$f\left(v_{3i+2}\right)=3\left(0\le i\le \frac{n-3}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=\frac{n}{3}$ ；若$n\equiv 1\left(\mathrm{mod}3\right)$ ，则设$f\left(v_n\right)=2$ ，$f\left(v_{3i+2}\right)=3$ $\left(0\le i\le \frac{n-4}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=\frac{n+2}{3}+1$ ；若$n\equiv 2\left(\mathrm{mod}3\right)$ ，则令$f\left(v_{3i+2}\right)=3$ $\left(0\le i\le \frac{n-2}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=\frac{n+1}{3}+1$ 。根据以上赋值条件可知：当$n\equiv 0,2\left(\mathrm{mod}3\right)$ 时，$P_n$ 上的所有点均用−1和3交替赋值，则满足ISDRDF的四个条件；当$n\equiv 1\left(\mathrm{mod}3\right)$ 时，$P_n$ 上的所有点除了顶点$v_n$ 赋值为2，其余顶点均用−1和3交替赋值。又有$f\left[v_n\right]=1$ ，从而满足ISDRDF的四个条件。因此$f$ 是$P_n$ 的ISDRDF，综上可知当$n\equiv 0\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(P_n\right)\le \frac{n}{3}$ ；当$n\ne 0\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(P_n\right)\le \lceil \frac{n}{3}\rceil +1$ 。

由结论1有$i_{sdR}\left(G\right)\ge {\gamma }_{sdR}\left(G\right)$ ，故该推论成立。 □

引理5 [22]：设$G$ 为$C_n$ ，对于$n\ge 3$ ，${\gamma }_{sdR}\left(C_n\right)=\{\begin{array}{l} \frac{n}{3},若n\equiv 0\left(\mathrm{mod}3\right),\hfill \\ \lceil \frac{n}{3}\rceil +2,若n\equiv 1\left(\mathrm{mod}3\right),\hfill \\ \lceil \frac{n}{3}\rceil +1,若n\equiv 2\left(\mathrm{mod}3\right)。\hfill \end{array}$

推论6：设$G$ 为$C_n$ ，对于$n\ge 3$ ，$i_{sdR}\left(C_n\right)=4\times \lceil \frac{n}{3}\rceil -n={\gamma }_{sdR}\left(C_n\right)$ 。

证明：先证$i_{sdR}\left(C_n\right)\le {\gamma }_{sdR}\left(C_n\right)$ 。设$C_n=v_1{v}_2\cdots v_n{v}_1$ ，定义$f:V\left(C_n\right)\to \left\{-1,1,2,3\right\}$ 如下，若$n\equiv 0\left(\mathrm{mod}3\right)$ ，则令$f\left(v_{3i+2}\right)=3\left(0\le i\le \frac{n-3}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=4\times \frac{n}{3}-n=\frac{n}{3}$ ；若$n\equiv 1\left(\mathrm{mod}3\right)$ ，则设$f\left(v_n\right)=3$ ，$f\left(v_{3i+2}\right)=3\left(0\le i\le \frac{n-4}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=4\times \frac{n+2}{3}-n$ $=4\times \lceil \frac{n}{3}\rceil -n$ ；若$n\equiv 2\left(\mathrm{mod}3\right)$ ，则令$f\left(v_{3i+2}\right)=3\left(0\le i\le \frac{n-2}{3}\right)$ ，否则$f\left(x\right)=-1$ ，此时$w\left(f\right)=4\times \frac{n+1}{3}-n=4\times \lceil \frac{n}{3}\rceil -n$ 。根据以上赋值条件可知：当$n\equiv 0,1,2\left(\mathrm{mod}3\right)$ 时，$C_n$ 上的所有点均用−1和3交替赋值，则满足ISDRDF的四个条件。因此$f$ 是$C_n$ 的ISDRDF，则$i_{sdR}\left(C_n\right)\le 4\times \lceil \frac{n}{3}\rceil -n$ ，即$i_{sdR}\left(C_n\right)\le {\gamma }_{sdR}\left(C_n\right)$ 。

又由结论1，有$i_{sdR}\left(G\right)\ge {\gamma }_{sdR}\left(G\right)$ 。因此当$n\equiv 0\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(C_n\right)\ge \frac{n}{3}=4\times \frac{n}{3}-n$ ；当$n\equiv 1\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(C_n\right)\ge \lceil \frac{n}{3}\rceil +2=4\times \left(\frac{n-1}{3}+1\right)-n$ ；当$n\equiv 2\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(C_n\right)\ge \lceil \frac{n}{3}\rceil +1=4\times \left(\frac{n-2}{3}+1\right)-n$ 。综上可知，$i_{sdR}\left(C_n\right)=4\times \lceil \frac{n}{3}\rceil -n={\gamma }_{sdR}\left(C_n\right)$ 。 □

3.3. 完全图结果

在明确了$i_{sdR}\left(P_n\right)$ 与$i_{sdR}\left(C_n\right)$ 后，我们将进一步研究完全图。用$K_n$ 表示$n$ 个顶点上的完全图，其所有顶点两两相邻的特殊性质与$P_n$ 与$C_n$ 差异显著，必然会对$i_{sdR}\left(G\right)$ 产生影响。接下来，让我们深入探究$i_{sdR}\left(K_n\right)$ 的上界。

结论7：设$G$ 为$K_n$ ，对于$n\ge 3$ ，$i_{sdR}\left(K_n\right)$ 有以下结论成立：

1) 当$n\equiv 2\left(\mathrm{mod}3\right)$ ，$i_{sdR}\left(K_n\right)=1$ ；

2) 当$n\equiv 1\left(\mathrm{mod}3\right)$ ，$i_{sdR}\left(K_n\right)\le 2$ ；

3) 当$n\equiv 0\left(\mathrm{mod}3\right)$ ，$i_{sdR}\left(K_n\right)\le \{\begin{array}{l}3,若n\equiv 0,1\left(\mathrm{mod}4\right),\\ 2,若n\equiv 2\left(\mathrm{mod}4\right),\\ 1,若n\equiv 3\left(\mathrm{mod}4\right)。\end{array}$

证明：设$G=\left(V,E\right)$ 为完全图，考虑$f$ 是一个$i_{sdR}\left(K_n\right)$ -函数，对任意顶点$v\in V\left(G\right)$ ，有$w\left(K_n\right)=f\left[v\right]\ge 1$ ，故$i_{sdR}\left(K_n\right)=w\left(f\right)\ge 1$ 。

若$f=\left(V_{-1},V_1,V_2,V_3\right)=\left(V_{-1},\varnothing ,V_2,\varnothing \right)$ ，则假设将$t$ 个顶点赋值为2，$w\left(f\right)=3t-n$ ；若$f^{\prime }=\left(V_{-1},V_1,V_2,V_3\right)=\left(V_{-1},\varnothing ,\varnothing ,V_3\right)$ ，则假设将$t-a$ 个顶点赋值为3，$w\left(f^{\prime }\right)=4\left(t-a\right)-n$ 。令$w\left(f\right)\ge w\left(f^{\prime }\right)$ ，解得$a\ge \frac{t}{4}$ ，由于$a$ 为正整数，则$a\ge \lfloor \frac{t}{4}\rfloor$ 。

1) 当$n\equiv 2\left(\mathrm{mod}3\right)$ 时，则将$\frac{n+1}{3}$ 个顶点赋值为2，其余顶点赋值为−1。有：$w\left(K_n\right)\le 1$ ，因此，当$n\equiv 2\left(\mathrm{mod}3\right)$ ，$i_{sdR}\left(K_n\right)=1$ 。

2) 当$n\equiv 1\left(\mathrm{mod}3\right)$ 时，假设将$\frac{n+2}{3}$ 个顶点赋值为2，其余顶点赋值为−1，有$w\left(f\right)=2$ ；假设将$\frac{n+2}{3}-\lfloor \frac{\frac{n+2}{3}}{4}\rfloor$ 个顶点赋值为3，其余顶点赋值为−1，有$w\left(f^{\prime }\right)=4\times \left(\frac{n+2}{3}-\lfloor \frac{n+2}{12}\rfloor \right)-n$ ，整理$w\left(f^{\prime }\right)$ 可得$w\left(f^{\prime }\right)=2+4\times \frac{\left(n+2\right)}{12}-4\times \lfloor \frac{n+2}{12}\rfloor$ 。由向下整函数的定义，可知$0\le \frac{\left(n+2\right)}{12}-\lfloor \frac{n+2}{12}\rfloor \le 1$ ，则$w\left(f\right)\le w\left(f^{\prime }\right)$ 。因此$n\equiv 1\left(\mathrm{mod}3\right)$ 时，$i_{sdR}\left(K_n\right)$ -函数$f=\left(V_{-1},V_1,V_2,V_3\right)=\left(V_{-1},\varnothing ,V_2,\varnothing \right)$ 且$i_{sdR}\left(K_n\right)\le 2$ 。

3) 当$n\equiv 0\left(\mathrm{mod}3\right)$ 时，若将$\frac{n}{3}$ 个顶点赋值为2，其余顶点赋值为−1，有$w\left(f\right)=0<1$ ，不满足要求。假设将$\frac{n}{3}+1$ 个顶点赋值为2，其余顶点赋值为−1，有$w\left(f\right)=3$ ；若$\frac{n}{3}-\lfloor \frac{\frac{n}{3}}{4}\rfloor$ 个顶点赋值为3，其余顶点赋值为−1，有$w\left(f^{\prime }\right)=4\times \left(\frac{n}{3}-\lfloor \frac{n}{12}\rfloor \right)-n$ ，整理$w\left(f^{\prime }\right)$ 可得$w\left(f^{\prime }\right)=4\times \frac{n}{12}-4\times \lfloor \frac{n}{12}\rfloor \le 4$ 。在$n\equiv 0\left(\mathrm{mod}3\right)$ 的条件下，对同时满足$n\equiv 0\left(\mathrm{mod}4\right)$ 的情形展开进一步探讨：

情况1：假设$n\equiv 0\left(\mathrm{mod}4\right)$ ，若将$\lceil \frac{n}{4}\rceil$ 个顶点赋值为3，其余顶点赋值为−1，则$w\left(f\right)=0$ ，不满足要求；若$\lceil \frac{n}{4}\rceil +1$ 个顶点赋值为3，其余顶点赋值为−1，则$w\left(f\right)=4>3$ ，此时将$\frac{n}{3}+1$ 个顶点赋值为2的权重更小；

情况2：假设$n\equiv 1\left(\mathrm{mod}4\right)$ ，若将$\lceil \frac{n}{4}\rceil$ 个顶点赋值为3，其余顶点赋值为−1，则$w\left(f\right)=3$ ；

情况3：假设$n\equiv 2\left(\mathrm{mod}4\right)$ ，若将$\lceil \frac{n}{4}\rceil$ 个顶点赋值为3，其余顶点赋值为−1，则$w\left(f\right)=2$ ；

情况4：假设$n\equiv 3\left(\mathrm{mod}4\right)$ ，若将$\lceil \frac{n}{4}\rceil$ 个顶点赋值为3，其余顶点赋值为−1，则$w\left(f\right)=1$ 。

综上，当$n\equiv 0\left(\mathrm{mod}3\right)$ 时，有$i_{sdR}\left(K_n\right)\le \{\begin{array}{l}3,若n\equiv 0,1\left(\mathrm{mod}4\right),\\ 2,若n\equiv 2\left(\mathrm{mod}4\right),\\ 1,若n\equiv 3\left(\mathrm{mod}4\right)。\end{array}$ □

3.4. 独立符号双罗马控制问题的完全性

在分析完$i_{sdR}\left(P_n\right)$ 、$i_{sdR}\left(C_n\right)$ 与$i_{sdR}\left(K_n\right)$ 的独立符号双罗马控制数分析后，我们将通过证明IDSRD问题对于二部图是NP-完全的，从而揭示其内在复杂性特征。

IDSRD问题

实例：图$G=\left(V,E\right)$ ，正整数$k\le \left|V\right|$ 。

问题：$G$ 是否有一个权重至多为$k$ 的IDSRDF？

Hickey [23]等人证明了$X3C3$ 是NP-完全的，因此我们可以通过将$X3C3$ 归约为IDSRD，从而证明IDSRD问题是NP-完全的。

$X3C3$

实例：假设存在一个大小为$3q$ 的集合$X$ 和$X$ 的三个元素子集的集合$C=\left\{C_1,\cdots ,C_{3q}\right\}$ ，使得每个元素$x_i\in X$ 正好在$C$ 的三个子集中。

问题：$C$ 是否包含$X$ 的一个精确覆盖，即$C$ 是否存在一个子集合$C^{\prime }\subset C$ ，使得$X$ 中的每个元素$x_i\in X$ 都恰好在$C^{\prime }$ 的一个元素中？

现将$X3C3$ 归约为IDSRD问题，则当且仅当第二个实例有解时，第一个实例有解。

定理8：独立符号罗马双控制问题对于二部图是NP-完全的。

证明：因为可以在多项式时间内验证一个函数$f:V\to \left\{-1,1,2,3\right\}$ 是否是IDSRDF并且其权重至多为$k$ ，所以IDSRD问题是NP的。设$X = \left\{x_1,\cdots ,x_{3q}\right\}$ ，$C = \left\{C_1,\cdots ,C_{3q}\right\}$ 是$X3C3$ 的一个实例。设集合$W=\left\{w_1,w_2,\cdots ,w_{3q}\right\}$ 和$Z=\left\{c_1,c_2,\cdots ,c_{3q}\right\}$ 。对于集合$X$ 中的顶点$x_i$ ，创建一条路$P_2=x_i{w}_i$ 。构造一个顶点集为$V=\left\{v_1^j,v_2^j,\cdots ,v_8^j\right\}$ ，边集为$E=\left\{v_1^j{v}_2^j,v_2^j{v}_3^j,v_3^j{v}_4^j,v_4^j{v}_5^j,v_5^j{v}_6^j,v_6^j{v}_7^j,v_7^j{v}_8^j,v_8^j{v}_1^j,v_1^j{v}_4^j,v_3^j{v}_6^j,v_6^j{v}_8^j\right\}$ 的图${\Gamma }_j$ 。对每一个$c_j\in C$ ，可通过在图${\Gamma }_j$ 的基础上添加两条边$c_j{v}_1^j$ ，$c_j{v}_3^j$ 来构造了一个图$H_j$ 。如果$x_i\in C_j$ ，我们可以通过添加边$c_j{x}_i$ ，得到一个图$G$ 。显然这个$G$ 是一个二部图，设$k=25q$ ，图1是$q=2$ 的一个图$G$ 。

Figure 1. A graph $G$ with $q=2$

图1. $q=2$ 的一个图$G$

假设$X3C3$ 的实例存在一个解$C^{\prime }$ 。下面在$G$ 上构造一个权为$k$ 的独立符号双罗马控制函数，构造方法如下：1) 将值−1和2分别赋值给每个$x_i$ 和$w_i$ ；2) 对于每个$c_j\in C^{\prime }$ ，将2赋值给$c_j$ ，$v_1^j$ ，$v_3^j$ ；将3赋值给$v_5^j$ ，$v_7^j$ ；并将−1赋值给$H_j$ 的其余顶点；3) 对于每个$c_j\notin C^{\prime }$ ，将值3给$v_1^j$ ，$v_3^j$ ，$v_4^j$ ，$v_6^j$ ，并将−1赋给$H_j$ 的其余顶点。因为已知$X3C3$ 实例是存在一个解集$C^{\prime }$ 的，且$C$ 中的每一个元素都会对应$X$ 中的三个元素，$X$ 中的每个元素也正好在$C$ 的三个子集中。所以在精确覆盖的前提下，$X$ 中的$3q$ 个元素必然对应$q$ 个$C^{\prime }$ 中的元素，即$\left|C^{\prime }\right|=q$ ，因此集合$Z$ 中$c_j$ 的基数为$q$ 赋值为2且每一个$w_i$ 都赋值为2。而$C^{\prime }$ 是$X3C3$ 的解，所以$X$ 中的每个顶点都与两个赋值为2的顶点相邻。根据以上赋值条件可知：每个顶点$x_i$ 均赋值为−1且都与两个赋值为2的顶点相邻；$H_j$ 中赋值为2和3的顶点之间均没有连线而$H_j$ 中赋值为−1其余顶点经检验均满足要求，函数$f$ 满足ISDRDF的四条约束。因此函数$f$ 是一个ISDRDF，其权重为$f\left(V\right)= 7\times \left(3q-q\right)+8q+\left(-1+2\right)\times 3q=25q=k$ 。

反之，假设$G$ 有一个权重最大为$k$ 的IDSRDF。设图$H$ 是由图$G$ 的顶点子集$\left\{v_1^j,v_2^j,\cdots ,v_8^j\right\}$ 所生成的点导出子图，图$R$ 是由图$G$ 的顶点子集$\left\{x_i,w_i\right\}$ 所生成的点导出子图。定义$i_{sdR}\left(G\right)$ -函数$g =\left(V_{-1},V_1,V_2,V_3\right)$ ，使得$V_1=\varnothing$ ，且满足如下条件：

1) $\left|X\cap V_{-1}\right|$ 被最大化；

2) 受条件(1)约束：$\left|Z\cap V_3\right|$ 被最小化；

3) 根据条件(1)和(2)：$\left|W\cap V_3\right|$ 被最小化。

因此作如下要求：

a) 由于$C$ 中的每一个元素都会对应$X$ 中的三个元素，因此当$g\left(c_j\right)=-1$ 和$g\left(c_j\right)\ne -1$ 时，子图$H_j$ 上所对应的最优赋值方案如图2所示，则$g\left(H_j\right)=\{\begin{array}{l}7,g\left(c_j\right)=-1,\\ 8,g\left(c_j\right)\ne -1。\end{array}$ ；

Figure 2. The optimal assignment scheme related to $g\left(c_j\right)$ on the subgraph $H_j$

图2. 子图$H_j$ 上与$g\left(c_j\right)$ 相关的最优赋值方案

b) 由(a)，任意顶点$c_j$ 都不需要被顶点$x_i$ 保护，且子图$H_j$ 上有：$g\left(N\left[c_j\right]\right)=\{\begin{array}{l}5,g\left(c_j\right)=-1,\\ 6,g\left(c_j\right)\ne -1。\end{array}$ ；

c) 任意顶点$x_i$ 都不被赋值为2或3。事实上，不妨设$X$ 中的某一顶点$x_1$ ，若$g\left(x_1\right)= 2$ ，则$x_1$ 对应的邻点$w_1$ ，有：$g\left(w_1\right)= 2$ ，根据(b)，此时权重$w\left(x_1{w}_1\right)=4$ ；若$g^{\prime }\left(x_1\right)=3$ ，则$x_1$ 对应的邻点$w_1$ ，有：$g^{\prime }\left(w_1\right)=-1$ ，根据(b)，此时权重$w^{\prime }\left(x_1{w}_1\right)=2<w\left(x_1{w}_1\right)$ ；而$N\left(x_1\right)\cap Z$ 的一个顶点赋值大于等于2，则通过重新分配定义$g^{″}=\left(V_{-1}\cup \left\{x_1\right\}\backslash \left\{w_1\right\},V_1,V_2\cup \left\{w_1\right\},V_3\backslash \left\{x_1\right\}\right)$ 。显然函数$g^{″}$ 的权重比函数$g$ 和函数$g^{\prime }$ 的权重更小，矛盾。从而$X$ 中有更多顶点被赋值了−1；

d) 任意顶点$c_j$ 都不被赋值为3。事实上，不妨设$Z$ 中某一顶点$c_1$ ，有$g\left(c_1\right)= 3$ ，则由(a)可得$g\left(V\left(H_1\right)\right)=8$ 。

下面在图$G$ 上定义一个新的$i_{sdR}\left(G\right)$ -函数$g^{\prime }=\left(V_{-1},V_1,V_2,V_3\right)$ 通过赋值$g\left(c_1\right)=g\left(v_1^1\right)=g\left(v_3^1\right)=2$ ，$g\left(v_6^1\right)=g\left(v_8^1\right)=3$ ，$g\left(v_2^1\right)=g\left(v_4^1\right)=g\left(v_6^1\right)=g\left(v_8^1\right)=-1$ ，并且对任意顶点$v\in \left\{G\backslash H_1\right\}$ ，有$g^{\prime }\left(v\right)=g\left(v\right)$ 。

此时$w\left(g^{\prime }\right)=w\left(g\right)$ ，故当集合$Z$ 中有赋值为3的顶点时，可以用一个权重相同的独立符号双罗马控制函数$g^{\prime }$ 对其进行替换，从而任意顶点$c_j$ 都不被赋值为3；

e) 任意顶点$w_i$ 都不被赋值为3。事实上，由(b)项和独立符号双罗马控制函数的定义，任意一个顶点$x_1\in X$ 与$Z$ 中三个顶点相邻，其中两个顶点被赋值为−1，一个顶点被赋值为2的顶点。此时满足：$\sum f\left(N\left[x_i\right]\right)\ge 1$ ，即：$f\left(w_i\right)\ge 2$ 。要使得整体权重之和较小，因此$f\left(w_i\right)=2$ 。否则将会影响$C^{\prime }$ 中$c_j$ 的赋值，矛盾。

因此，根据前面的条件，可以得出$X\subset V_{-1}$ ，$Z\cap V_3=\varnothing$ ，$W\cap V_3=\varnothing$ 。因此，$Z\subset V_2$ 。显然$Z\cap V_2\ne \varnothing$ ，不妨设$b=\left| Z\cap V_2\right|$ ，而$C$ 中的每个顶点在$W$ 中正好有三个邻居，则$b \ge q$ 。此外，由于$g\left(V\left(H\right)\right)+ g\left(V\left(R\right)\right)= 7\times \left(3q-b\right)+8b+\left(-1+2\right)\times 3q\le 25q$ ，有$b \le q$ ，因此$b = q$ 。又由于每个$c_j$ 在$X$ 中正好有三个近邻，故$C^{\prime }=\left\{C_j:g\left(c_j\right)=2\right\}$ 是$C$ 的精确覆盖。 □

4. 总结与展望

本研究定义了图$G$ 上的ISDRDF，要求函数$f:V\left(G\right)\to \left\{-1,1,2,3\right\}$ 满足特定邻域条件且正权重顶点集为独立集，其最小权值为$i_{sdR}\left(G\right)$ 。

我们首先根据$i_{sdR}\left(G\right)$ 和${\gamma }_{sdR}\left(G\right)$ 的关系，推导出了$i_{sdR}\left(P_n\right)$ 和$i_{sdR}\left(C_n\right)$ 的值在不同情况下的具体表达式。接着我们探讨了$i_{sdR}\left(K_n\right)$ 的上界，根据三种不同情况分别给出结果。最后我们通过将$X3C3$ 问题归约，证明了二部图上ISDRD是NP-完全的。

这个研究结果为图的控制理论提供了新视角，未来ISDRDF的研究可进一步探索在其他图类上的$i_{sdR}\left(G\right)$ 及相关算法优化。由于独立符号双罗马控制融合了IDRD的独立性约束与SDRD的权重灵活性，未来可以在需要“非相邻节点协同”且“动态平衡资源损益”的场景中发挥作用。例如，在城市公共设施布局中，独立条件可确保公园、医疗站等设施分布在非相邻区域以均衡服务范围，负权重代表设施建设与维护成本，正权重代表设施的服务覆盖强度，该模型可辅助规划部门在有限预算内选择最优设施点位，既避免资源浪费在相邻区域，又实现服务覆盖与成本消耗的动态平衡。

基金项目

本研究得到了国家自然科学基金(编号：11701059)和重庆市自然科学基金创新发展联合基金(市教委) (编号：CSTB2022NSCQ-LZX0003)的资助。

NOTES

^*通讯作者。