一类仙人掌图的意大利支配问题

Italian Domination Problem in a Class of Cactus Graphs

摘要: 意大利支配问题是图论中经典支配属的一个变体。图$G$ 的一个意大利支配函数，是函数$f:V\to \left\{0,1,2\right\}$ ，满足对任意$f\left(v\right)=0$ 的顶点$v\in V$ ，有${\displaystyle {\sum }_{u\in N\left(v\right)}f\left(u\right)}\ge 2$ 。图$G$ 的一个意大利支配函数的权重之和为$f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ ，意大利支配数${\gamma }_I\left(G\right)$ 是一个意大利函数的最小权。本文针对等距m-仙人掌链的意大利支配问题，给出了其意大利数的计算公式。对于任意m-仙人掌链，给出了其意大利支配数的上界与下界，且发现了该类图一系列具有极值特性的链结构。

Abstract: The Italian domination problem is a variant of the classical domination property in graph theory. An Italian dominating function of a graph $G$ is a function $f:V\to \left\{0,1,2\right\}$ such that for every vertex $v\in V$ with $f\left(v\right)=0$ , the condition ${\displaystyle {\sum }_{u\in N\left(v\right)}f\left(u\right)}\ge 2$ holds. The weight of an Italian dominating function of $G$ is defined as $f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ , and the Italian domination number ${\gamma }_I\left(G\right)$ is the minimum weight among all Italian dominating functions. This paper addresses the Italian domination problem for isometric m-cactus chains. We establish an exact formula for the Italian domination number of such chains. For arbitrary m-cactus chains, we derive both upper and lower bounds for their Italian domination number. Furthermore, we identify a family of chain structures within this graph class that exhibit extremal properties.

1. 引言

意大利支配问题的研究由M. Chellai、T. W. Haynes等人[1]在2016年首次提出，并给出了罗马$\left\{2\right\}$ -支配数与其他支配数的界限，证明了意大利支配的相关决策问题是NP-完全。2017年Henning等人[2]描述了满足${\gamma }_I\left(T\right)=\gamma \left(T\right)+1$ 和${\gamma }_I\left(T\right)=2\gamma \left(T\right)$ 的树，$\gamma \left(T\right)$ 是经典支配数，其定义见第二节。2019年Gonzalez Yero等人[3]给出了树$T$ 满足${\gamma }_I\left(T\right)={\gamma }_R\left(T\right)$ 的构造特征，${\gamma }_R\left(T\right)$ 是罗马支配数，见定义1。2019年高红等人[4]对于广义Petersen图$P\left(n,3\right)$ 证明了当$n\equiv 0,4\left(\mathrm{mod}5\right)$ 或$n=8$ 时，有${\gamma }_I\left(P\left(n,3\right)\right)=\lceil \frac{4n}{5}\rceil$ ；否则${\gamma }_I\left(P\left(n,3\right)\right)=\lceil \frac{4n}{5}\rceil +1$ 。同年，高红等人[5]采用装箱和划分的方法研究了环与路径的笛卡尔积的意大利支配数，精确确定了${\gamma }_I\left(C_n\square P_3\right)$ 和${\gamma }_I\left(C_3\square P_n\right)$ 的意大利支配数，并给出了$n,m\ge 4$ 时${\gamma }_I\left(C_n\square P_m\right)$ 的上下界。同年，Volkmann等人[6]还研究了有向图的意大利支配问题，证明了$n$ 阶有向图有${\gamma }_I\left(D\right)\ge \lceil \frac{2n}{2+{\Delta }^{+}\left(D\right)}\rceil$ ；${\gamma }_I\left(D\right)\le n$ ，等号成立当且仅当${\Delta }^{+}\left(D\right),{\Delta }^{-}\left(D\right)\le 1$ 。还证明了如果$D$ 是阶数为$n$ 的有向图或者有向环，则${\gamma }_I\left(D\right)=n$ 。2020年A. Poureidi等人[7]证明了意大利支配相关的相关决策问题是NP-完全的，即使限制在平面图，同时提出了计算单环图意大利支配数的线性算法。2020年Henning等人[8]证明了若图$G$ 是阶数$n\ge 3$ 的连通图，则意大利支配数${\gamma }_I\le \frac{3}{4}n$ 在这个界内达到相等的图；若图$G$ 的最小度至少为2，则${\gamma }_I\left(G\right)\le \frac{2n}{3}$ ，并进一步研究了达到这些界限的连通图特征。此外建立了意大利支配数的Nordhaus-Gadum型不等式，该不等式提供给了图$G$ 及其补图参数的和(或积)的极值。2021年Van Bommel等人[9]完成了关于有向环笛卡尔积的意大利支配问题数的研究。

若图中的块是一个圈或是一条边，且两个块的交点为空集或是一个割点，则称该图为仙人掌图，如图1。仅有一个环的仙人掌图称为独车轮，没有环的仙人掌图称为树。只有环且割点仅连接2个环的仙人掌图称为仙人掌链。

仙人掌图的研究起源于20世纪50年代K. Husimi [10]等人首次提出，并称它为Husimi树。1953年F. Harary等人[11]研究了Cayley数的计数方法，沿用了Husimi树的名称并且研究其计数问题。他们考虑了点可区分和点不可区分两种情况，利用生成函数和Polya计数理论，建立了纯Husimi树和混合Husimi树的函数方程，并给出了若干具体类型的计数公式。2005年Ben-Moshe B等人[12]解决了仙人掌图中加权中心问题的有效算法；提出了一种$O\left(n\log n\right)$ 时间算法，该算法在仙人掌图中找到加权1中心，其中$n$ 是图中的顶点数；对于加权2中心问题，为其设计了一种$O\left(n{\log }^{3}n\right)$ 时间算法，并表明在$O\left(n{\log }^{2}n\right)$ 时间内是可求解的，且改进了之前的$O\left(cn\right)$ 结果，其中$c$ 是图中使用的不同顶点权重的数量。同年B. Zmazek等人[13]给出了一种线性算法，用于计算加权仙人掌图上所有延迟的总和，讨论了计算仙人掌维纳多项式的复杂性。

Figure 1. Cactus graph

图1. 仙人掌图

2. 基础知识

本文中所涉及的图均为无向的简单图。设$G=\left(V,E\right)$ 表示一个图，其中$V\left(G\right)$ 和$E\left(G\right)$ 分别表示图$G$ 的点集和边集，图$G$ 的顶点数和边数分别用$n\left(G\right)$ 和$m\left(G\right)$ 表示。$G$ 中两个顶点$v$ 和$u$ 之间的距离，记作$d_G\left(u,v\right)$ ，是$G$ 中的一条$\left(u,v\right)$ -路径的最小长度。$G$ 的直径$diam\left(G\right)$ 是$G$ 中顶点对之间的最大距离。$G$ 中的一条直径路径是其最短路径，它的长度等于图的直径。顶点$v\in V\left(G\right)$ 的开邻域是集合$N\left(v\right)=\left\{u:uv\in E\right\}$ ，闭邻域是集合$N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$ 。用$d_G\left(v\right)$ 或者$d\left(v\right)$ 表示$G$ 中顶点$v$ 的度。设$\delta \left(G\right)$ 和$\Delta =\Delta \left(G\right)$ 分别表示$G$ 中顶点的最小度和最大度。在移除点$v$ 之后如果连通分支的数量增加，则点$v$ 是一个割点。设子集$S\subseteq V$ ，如果任意$v\in V$ 是$S$ 的一个元素或与$S$ 的一个元素相邻，则称子集$S$ 为支配集[14]。支配数$\gamma \left(G\right)$ 是$G$ 的所有支配集中的最小数。设子集$S\subseteq V$ ，如果任意顶点$w\in V\backslash S$ ，$\left|N_G\left(w\right)\cap S\right|\ge 2$ ，则$S$ 为2-支配集。2-支配数${\gamma }_2\left(G\right)$ 是 $G$ 中所有2-支配集中的最小数[15] [16]。

定义1 [1]：图$G=\left(V,E\right)$ 的函数$f:V\left(G\right)\to \left\{0,1,2\right\}$ ，满足对任意$f\left(v\right)=0$ 的顶点$v\in V$ ，至少存在一个邻点$u$ 且$f\left(u\right)=2$ ，则称$f$ 为$G$ 的一个罗马支配函数。该函数的权值定义为$f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ 。所有罗马支配函数中的最小权重称为图$G$ 的罗马支配数，记为${\gamma }_R\left(G\right)$ 。

定义2 [1]：图$G=\left(V,E\right)$ 的函数$f:V\left(G\right)\to \left\{0,1,2\right\}$ ，满足对任意$f\left(v\right)=0$ 的顶点$v\in V$ ，均有${\displaystyle {\sum }_{u\in N\left(v\right)}f\left(u\right)}\ge 2$ ，则称$f$ 为$G$ 的一个意大利支配函数。该函数的权值定义为$f\left(V\right)={\displaystyle {\sum }_{u\in V}f\left(u\right)}$ 。所有意大利支配函数中的最小权重称为图$G$ 的意大利支配数，记为${\gamma }_I\left(G\right)$ ，达到该最小权值的函数称为的${\gamma }_I$ -函数。

定义3 [17]：设图$G=\left(V,E\right)$ ，若函数$f:V\to \left\{0,1,2\right\}$ ，满足对于每个$f\left(v\right)=0$ 的顶点$v$ ，均存在邻点$u\in N\left(v\right)$ 且满足$f\left(u\right)>0$ ，使得函数$f^{\prime }$ (定义为$f^{\prime }\left(u\right)=f\left(u\right)-1$ ，$f^{\prime }\left(v\right)=f\left(v\right)+1$ ，且其余顶点赋值不变)仍为支配函数，则称$f$ 为$G$ 的弱罗马支配函数。该函数的权值定义为$w\left(f\right)={\displaystyle {\sum }_{v\in V}f\left(v\right)}$ ，而图$G$ 的弱罗马支配数${\gamma }_r\left(G\right)$ 是所有弱罗马支配函数中的最小权重值。

设$f=\left(V_0,V_1,V_2\right)$ 是图$G=\left(V,E\right)$ 上的函数$f:V\to \left\{0,1,2\right\}$ ，其中$V_i=\left\{v|f\left(v\right)=i\right\},i\in \left\{0,1,2\right\}$ 。定义$D=V_1$ ，即$D$ 是每个权重为1的顶点的集合。

定义4 [18]：m-仙人掌链[15]是一种仙人掌图，其中所有环都具有$m$ 个顶点。设$G_m^h$ 表示一个长度为$h$ 的m-仙人掌链，记作：$G_m^h=C_m^1{C}_m^2{C}_m^3\cdots C_m^h$ ，其中$C_m^1$ 和$C_m^h$ 为终端环，且满足：

1) 对于$i=1,\cdots ,h-1$ ，环$C_m^i$ 和$C_m^{i+1}$ 有一个公共顶点；

2) 每个顶点至多属于两个环。

对任意$k\ge 1$ 和$t\le h$ ，子图$C_m^{k+1}\cdots C_m^{k+t}$ 称为$G_m^h$ 的一个子链。对环$C_m^i$ 与$C_m^{i+1}$ ($i=1,2,\cdots ,h-2$ )定义其距离$d_m^i$ 为：$d_m^i:=\min \left\{d\left(y,w\right)|y\in V\left(C_m^i\right),w\in V\left(C_m^{i+2}\right)\right\}$ ，其中$d\left(y,w\right)$ 表示顶点$y$ 与$w$ 在图中的最短路径长度。若$G_m^h$ 满足：$d_m^1=d_m^2=\cdots =d_m^{h-2}=c$ ，$\left(1\le c\le \lfloor \frac{m}{2}\rfloor \right)$ ，则称为等距m-仙人掌链，记作$E{G}_m^h$ 。如图2的右图。

Figure 2. The left side shows a 12-Cactus Chain $G_{12}^5$ ; the right side shows an Equidistant 7-Cactus Chain $E{G}_7^4$

图2. 左图：仙人掌链$G_{12}^5$ ；右图：等距仙人掌链$E{G}_7^4$

命题1 [1]：对任意图$G$ ，都有$\gamma \left(G\right)\le {\gamma }_r\left(G\right)\le {\gamma }_I\left(G\right)\le {\gamma }_{r2}\left(G\right)\le {\gamma }_R\left(G\right)\le 2\gamma \left(G\right)$ 。

命题2 [1]：对任意$m$ 阶的环$C_m$ ，其意大利支配数为${\gamma }_I\left(G\right)=\lceil \frac{m}{2}\rceil$ 。

命题3 [1]：图$G$ 为满足$\Delta \left(G\right)\le 2$ 的图，其${\gamma }_I\left(G\right)={\gamma }_2\left(G\right)$ 。

推论1：设图$G$ 是一个$m$ 阶的环，有${\gamma }_I\left(C_m\right)={\gamma }_2\left(C_m\right)=\lceil \frac{m}{2}\rceil$ 。

证明：由命题2可知，其意大利支配数为${\gamma }_I\left(C_m\right)=\lceil \frac{m}{2}\rceil$ 。由于环中每个顶点的度均为2，即满足$\Delta \left(G\right)=2$ 。再根据命题3可知${\gamma }_I\left(C_m\right)={\gamma }_2\left(C_m\right)$ 。因此，有${\gamma }_I\left(C_m\right)={\gamma }_2\left(C_m\right)=\lceil \frac{m}{2}\rceil$ 。 □

进一步地，设$f=\left(V_0,V_1,V_2\right)$ 为$C_m$ 的一个${\gamma }_I$ -函数，即达到最小权重$\lceil \frac{m}{2}\rceil$ 。若存在某个顶点被赋值为2，即$V_2\ne \varnothing$ ，则其支配能力未能被完全利用，将导致总权重大于$\lceil \frac{m}{2}\rceil$ ，与最小性矛盾。故$V_2=\varnothing$ 。此时，在$C_m$ 的任意一个${\gamma }_I$ -函数中，所有顶点赋值均来自集合$\left\{0,1\right\}$ 。为满足定义1，即每个赋值为0的顶点必须邻接两个赋值为1的顶点，所有采用“1”和“0”交替的赋值模式，即不存在两个连续的0顶点。此时总权重恰好为$\lceil \frac{m}{2}\rceil$ ，且构成一个意大利支配函数，同时也是2-支配函数。

推论2：设图$G$ 是m-仙人掌链且$\Delta \left(G\right)=4$ ，设$f=\left(V_0,V_1,V_2\right)$ 为$G$ 的一个${\gamma }_I$ -函数，则$V_2=\varnothing$ 。

证明：设图$G=G_m^h$ 是一个由$h$ 个$m$ 阶环构成的仙人掌链。

当$h=1$ 时，$G$ 为环$C_m$ 由命题2与命题3可知，结论成立。

当$h\ge 2$ 时，存在一个最小的意大利支配函数$f$ 满足$V_2\ne \varnothing$ ，即存在顶点$v\in V$ 使得$f\left(v\right)=2$ 。由于最大度$\Delta \left(G\right)=4$ ，存在顶点$v$ 的邻点集合$N\left(v\right)$ 包含最多4个顶点。

情况1：$v$ 是割点，即度数为4。

子情况1.1：$N\left(v\right)$ 中存在至少有一个顶点$u$ 满足$f\left(u\right)\ge 1$ ，即$f\left(u\right)=1$ 或2。现在构造一个新函数$f^{\prime }$ ：$f^{\prime }\left(v\right)=1$ ，$f\left(y\right)=f^{\prime }\left(y\right)$ ，$y\in \left(V\backslash v\right)$ 。则权重变化$w\left(f^{\prime }\right)=w\left(f\right)-1$ ，因为$f\left(v\right)$ 从2减少到1，而其他顶点赋值不变。对于顶点$v$ 由其本身支配；对于$v$ 的邻点$u$ ，由于$f\left(u\right)\ge 1$ ，调整后$f^{\prime }\left(u\right)=f\left(u\right)\ge 1$ ，因此$u$ 的支配性不受影响；其余顶点赋值不变，因此支配性保持。由于仙人掌链中除割点外的顶点度为2，因此$v$ 的邻点$u$ 必有其他邻点，就可以让其他顶点补偿，确保其权重和$\ge 2$ 。因此函数$f^{\prime }$ 满足意大利支配函数的条件，且$w\left(f^{\prime }\right)<w\left(f\right)$ ，与$f$ 最小性矛盾。

子情况1.2：所有邻点$u\in N\left(v\right)$ 满足$f\left(u\right)=0$ 。此时，由于$f$ 是意大利支配函数，每个$u\in N\left(v\right)$ 满足${\displaystyle \sum _{w\in N\left(u\right)}f\left(w\right)}\ge 2$ 。但$f\left(v\right)=2$ 可支配这些$u$ 。$v$ 是割点，连接两个$m$ 阶环$C_1$ 和$C_2$ 。每个环的意大利支配数${\gamma }_I\left(C_i\right)=\lceil \frac{m}{2}\rceil$ 。$G$ 的意大利支配数上界：${\gamma }_I\left(G\right)\le {\gamma }_I\left(C_1\right)+{\gamma }_I\left(C_2\right)-1=2\lceil \frac{m}{2}\rceil -1$ 。此时，权重为$w\left(f\right)\ge w\left({f|}_{C_1}\right)+w\left({f|}_{C_2}\right)-f\left(v\right)$ 。由于$f\left(v\right)=2$ ，且环上权重至少为${\gamma }_I\left(C_i\right)$ ，有$w\left(f\right)\ge \lceil \frac{m}{2}\rceil +\lceil \frac{m}{2}\rceil -2=2\lceil \frac{m}{2}\rceil -2$ 。对于$m\ge 3$ ，有$2\lceil \frac{m}{2}\rceil -2<2\lceil \frac{m}{2}\rceil -1\le {\gamma }_I\left(G\right)$ 。但${\gamma }_I\left(G\right)$ 是最小权重，因此$w\left(f\right)$ 不可能小于${\gamma }_I\left(G\right)$ ，这与$f$ 的最小性矛盾。

情况2：$v$ 是非割点，即度数为2。

此时$v$ 属于每个环$C_m^i$ ，且度数为2，如果$f\left(v\right)=2$ ，则可以设一个新的函数$f^{\prime }$ ：$f^{\prime }\left(v\right)=1$ ，其邻点支配性不变。由于环的最小意大利支配函数是0和1交替赋值的，调整后$f^{\prime }$ 仍满足条件且$w\left(f^{\prime }\right)<w\left(f\right)$ ，与最小性矛盾。

综上，情况1和情况2都导出矛盾，因此假设错误，则$V_2\ne \varnothing$ 。 □

为了进一步研究仙人掌链的意大利支配结构，本文引入一个关键引理：

引理1：设图$G$ 是由$h$ 个$m$ 阶的环连接而成的仙人掌图。若$D$ 是$G_m^h$ 的一个最小意大利支配集，则$D$ 中包含$G_m^h$ 的所有割点。

证明：假设存在一个最小意大利支配集$D$ ，它不包含所有的割点。换而言之，至少存在一个割点$u_s$ ，$s\in \left\{1,2,\cdots ,h-1\right\}$ ，满足$u_s\notin D$ 。根据定义1，由于$u_s\notin D$ ，即$u_s$ 未被支配，则$u_s$ 必须被其邻点支配。设$v_1\in N\left(u_s\right)\cap C_m^s$ 和$v_2\in N\left(u_s\right)\cap C_m^{s+1}$ 是用于支配$u_s$ 的两个顶点，即$v_1,v_2\in D$ ，其中$C_m^s$ 和$C_m^{s+1}$ 分别表示第$s$ 个和第$s+1$ 个$m$ 阶环。现构造新集合$D^{\prime }=\left(D\backslash \left\{v_1,v_2\right\}\right)\cup \left\{u_s\right\}$ 。可以验证，$D^{\prime }$ 仍然是$G$ 的一个意大利支配集，也就是说，对于任意顶点$w\in V\left(G_m^h\right)$ ，如果$w\notin D^{\prime }$ ，则$w$ 的邻点中至少有两个顶点属于$D^{\prime }$ 。分情况讨论如下。

情况1：对于$w=u_s$ 。由于$u_s\notin D^{\prime }$ ，它自身被支配满足条件。

情况2：对于$w=v_1$ 或者$w=v_2$ 。这些顶点被从$D$ 中移除，但需要检查其支配性。以$v_1$ 为例，其邻点包括$v_s\in D^{\prime }$ 和环$C_m^s$ 上的其他顶点。由于$G_m^h$ 是仙人掌链，环中每个顶点的度至少为2。因此$v_1$ 的其他邻点可通过环上剩余顶点支配。类似论证$v_2$ 。对于其他顶点，$D^{\prime }$ 的改动仅限于$u_s$ 及其邻域，因此这些顶点的支配性不受影响。

因此$D^{\prime }$ 是一个意大利支配集。然而，新集合的大小满足$\left|D^{\prime }\right|=\left|D\right|-2+1=\left|D\right|-1<D$ ，这与$D$ 是最小意大利支配集的假设矛盾。故假设不成立，原命题的证，即任何最小的意大利支配集$D$ 必须包含所有割点。 □

下一节重点研究等距仙人掌链$E{G}_m^h$ 的意大利支配问题。利用其均匀的环间距与对称性，建立标记与参数约束建立的通用模型，并通过奇偶性分析其意大利支配集结构。值得注意的是割点在支配集中的必要性将称为证明最小性的核心依据。

3. $E{G}_m^h$ 的意大利支配数

首先用图3所示的方式标记$E{G}_m^h$ 的顶点，其中$z+t+2=m$ ，$z\le t$ 和$c=d\left(u_{i-1},u_i\right)$ 。

Figure 3. Vertex markers of equidistant cactus chains $E{G}_m^h$

图3. 等距仙人掌链$E{G}_m^h$ 的顶点标记

定理1：设$E{G}_m^h$ 是由环构成的等距仙人掌链，其中$h\ge 1$ ，$m\ge 3$ 。则意大利支配数为：

${\gamma }_I\left(E{G}_m^h\right)=\{\begin{array}{l}h\lceil \frac{m}{2}\rceil -h+1,m\equiv 1\left(\mathrm{mod}2\right)\\ h\cdot \frac{m}{2}-h+1,m\equiv 0\left(\mathrm{mod}2\right)且c\equiv 0\left(\mathrm{mod}2\right)\\ h\cdot \frac{m}{2}-\lfloor \frac{h}{2}\rfloor ,m\equiv 0\left(\mathrm{mod}2\right)且c\equiv 1\left(\mathrm{mod}2\right)\end{array}$

其中，参数$c$ 为链中相邻两环共享割点之间的路径长度(见图3)。

证明：当$h=1$ 时，图$E{G}_m^h$ 为一个简单的环$C_m$ 。由命题2知，结论成立。

当$h\ge 2$ 时，进一步分为两个子情况：

情形1：$m\equiv 1\left(\mathrm{mod}2\right)$ 。

子情形1.1：$c\equiv 0\left(\mathrm{mod}2\right)$ 。此时有$z\equiv 1\left(\mathrm{mod}2\right)$ 和$t\equiv 0\left(\mathrm{mod}2\right)$ 。对于每个环$C_m^i\left(i=1,2,\cdots ,h\right)$ 。定义其上的意大利支配集为$D_i=\left\{y_{2j}^i:j=1,2,\cdots ,\lfloor \frac{z}{2}\rfloor \right\}\cup \left\{x_{2j-1}^i:j=1,2,\cdots ,\frac{t}{2}\right\}$ 。整个仙人掌链的意大利支配集为$P_0=\left({\displaystyle {\cup }_{i=1}^h{D}_i}\right)\cup \left\{u_h\right\}$ 是$E{G}_m^h$ 。通过计算集合$P_0$ ，可以得到，${\gamma }_I\left(E{G}_m^h\right)\le \left|P_0\right|=h\lceil \frac{m}{2}\rceil -h+1$ 。

下面证明集合$P_0$ 是$E{G}_m^h$ 的所有意大利支配集中具有最小的意大利支配数。

由命题1知，${\gamma }_I\left(E{G}_m^h\right)\le {\gamma }_r\left(E{G}_m^h\right)$ 。现需证明${\gamma }_r\left(E{G}_m^h\right)\ge h\lceil \frac{m}{2}\rceil -h+1$ 。设$f$ 为$E{G}_m^h$ 的一个最小弱罗马支配函数，即$w\left(f\right)={\gamma }_r\left(E{G}_m^h\right)$ ，对于任意满足$f\left(v\right)=0$ 的顶点$v\in V\left(E{G}_m^h\backslash P_0\right)$ ，根据推论2知，该图知存在邻点$x$ 和$y$ ，且$f\left(x\right)=f\left(y\right)=1$ ，因此定义一个新的函数$f^{\prime }$ 。令$f^{\prime }\left(v\right)=1$ ，$f^{\prime }\left(x\right)=0$ 和$f^{\prime }\left(w\right)=f\left(w\right)$ ，其中$w$ 是其他顶点，不存在未被支配的顶点。因此新的函数$f^{\prime }$ 仍然是图$E{G}_m^h$ 的一个弱罗马支配函数，特别地，考虑割点邻域的结构，通过分析可知，为满足所有割点及其邻域的支配条件，函数$f$ 的权重至少为$h\lceil \frac{m}{2}\rceil -\left(h-1\right)$ 。若存在某个赋值的总权重更小，则可以通过上述函数变换构造出一个权重更小的弱罗马支配函数，这与$f$ 的最小性矛盾。因此，有${\gamma }_r\left(E{G}_m^h\right)\ge h\lceil \frac{m}{2}\rceil -h+1$ 。综上，即得${\gamma }_I\left(E{G}_m^h\right)=h\lceil \frac{m}{2}\rceil -h+1$ 。

子情形1.2：$c\equiv 1\left(\mathrm{mod}2\right)$ 。此时有$z\equiv 0\left(\mathrm{mod}2\right)$ 和$t\equiv 1\left(\mathrm{mod}2\right)$ 。对每个环$C_m^i,其中\left(i=1,2,\cdots ,h\right)$ ，定义$D_i=\left\{y_{2j-1}^i:j=1,2,\cdots ,\frac{z}{2}\right\}\cup \left\{x_{2j}^i:j=1,2,\cdots ,\lfloor \frac{t}{2}\rfloor \right\}$ 。令$P_1=\left({\displaystyle {\cup }_{i=1}^h{D}_i}\right)\cup \left(u_h\right)$ ，该集合是$E{G}_m^h$ 的一个意大利支配集。通过计算集合$P_1$ ，可以得到${\gamma }_I\left(E{G}_m^h\right)\le \left|P_1\right|=h\lceil \frac{m}{2}\rceil -h+1$ 。

${\gamma }_I\left(E{G}_m^h\right)\ge h\lceil \frac{m}{2}\rceil -h+1$ 证明其证明过程和情形1.1一样。

图4给出了$m\equiv 1\left(\mathrm{mod}2\right)$ 的$E{G}_m^h$ 和相应的意大利支配集$P_r,r=0,1$ 的例子。红点表示赋值为1的顶点，黑点表示赋值为0的顶点，该证明中的几个例图中红、黑点表示意思一样。

Figure 4. $E{G}_m^h$ whit $m\equiv 1\left(\mathrm{mod}2\right)$ and their corresponding Italian dominating sets $P_r,r=0,1$

图4. $m\equiv 1\left(\mathrm{mod}2\right)$ 的$E{G}_m^h$ 和相应的意大利支配集$P_r,r=0,1$

情形2：$m\equiv 0\left(\mathrm{mod}2\right)$ ：

子情形2.1：$c\equiv 0\left(\mathrm{mod}2\right)$ 。此时有$z,t\equiv 1\left(\mathrm{mod}2\right)$ 。构造意大利支配集$R_0$ ，对每个环$C_m^i\left(i=1,2,\cdots ,h\right)$ ，定义集合$D_i=\left\{y_{2j}^i:j=1,2,\cdots ,\lfloor \frac{z}{2}\rfloor \right\}\cup \left\{x_{2j}^i:j=1,2,\cdots ,\lfloor \frac{t}{2}\rfloor \right\}$ 。整个图的支配集为$R_0=\left({\displaystyle {\cup }_{i=1}^h{D}_i}\right)\cup \left\{u_h\right\}$ 。该集合是$E{G}_m^h$ 的一个意大利支配集。通过计数可得$\left|R_0\right|=h\cdot \frac{m}{2}-h+1$ ，因此可以得到意大利支配数的上界，${\gamma }_I\left(E{G}_m^h\right)\le \left|R_0\right|=h\cdot \frac{m}{2}-h+1$ 。

下面证明集合$R_0$ 是$E{G}_m^h$ 的所有意大利支配集中具有最小的意大利支配数。

由引理1可知，$u_1,u_2,\cdots ,u_{h-1}\in D$ 。此时分析每个环所需的最小支配点数。首先对于中间环$C_m^j\left(j=2,\cdots ,h-1\right)$ ，每个环与前后共享两个割点$u_{j-1}$ 和$u_j$ 。环上需要支配的顶点剩余$m-2$ 个，如果$C_m^i\backslash \left\{u_i,y_z^i,x_t^i\right\}$ ，则至少需要$\frac{z-2}{2}+\frac{t-2}{2}=\frac{m}{2}-2$ 个支配点；其次对于首环$C_m^1$ ，与相邻环共享一个割点$u_1$ 。还需要支配其剩余$m-1$ 个顶点，如果$C_m^1\backslash \left\{u_1,y_z^1,x_t^1\right\}$ ，那么至少需要$\frac{m}{2}-1$ 个支配点；最后尾环$C_m^h$ 的情况与首个环相同。因此，整个支配集的最小数为：

${\gamma }_I\left(E{G}_m^h\right)\ge \left(\frac{m}{2}-1+1\right)+{\displaystyle \sum _{j=2}^{h-1}\left(\frac{m}{2}-2+1\right)}+\left(\frac{m}{2}-1+1\right)=h\cdot \frac{m}{2}-\left(h-2\right)$ (1)

注意到，在计算首环和尾环时，已经包含了割点$u_1$ 和$u_{h-1}$ ，但中间环的计算中，每个环的贡献已经扣除两个割点。该下界结果$h\cdot \frac{m}{2}-\left(h-2\right)$ 比$h\cdot \frac{m}{2}-\left(h-1\right)$ 更大，表明需要更精确的分析。实际上，首环和尾环所需的$\frac{m}{2}$ 个支配点，已经包含了割点，而中间环的$\frac{m}{2}-1$ 是不包含割点的。因此，其下界为：

${\gamma }_I\left(E{G}_m^h\right)\ge \left(\frac{m}{2}\right)+\left(h-2\right)\left(\frac{m}{2}-1\right)+\left(\frac{m}{2}\right)=h\cdot \frac{m}{2}-\left(h-2\right)$

然而，结合引理1，并且注意到中间环的$\frac{m}{2}-1$ 个支配点，已经包含了割点，因此该下界时紧的。

综合上述式子得到，${\gamma }_I\left(E{G}_m^h\right)=h\cdot \frac{m}{2}-\left(h-1\right)=h\frac{m}{2}-h+1$ 。

子情形2.2：$c\equiv 1\left(\mathrm{mod}2\right)$ 。此时有$z,t\equiv 0\left(\mathrm{mod}2\right)$ 。构造意大利支配集$R_1$ ，对每个环$C_m^i\left(i=1,2,\cdots ,h\right)$ ，定义支配集$D_{2i-1}=\left\{u_{2i-1}\right\}\cup \left\{y_{2j}^{2i-1}:j=1,2,\cdots ,\frac{z}{2}\right\}\cup \left\{x_{2j}^{2i-1}:j=1,2,\cdots ,\frac{t}{2}\right\}$ 和$D_{2i}=\left\{y_{2j-1}^{2i}:j=1,2,\cdots ,\frac{z}{2}\right\}\cup \left\{x_{2j-1}^{2i}:j=1,2,\cdots ,\frac{t}{2}\right\}$ 。有意大利支配集$R_1=\left({\displaystyle {\cup }_{i=1}^{\lceil \frac{h}{2}\rceil }{D}_{2i-1}}\right)\cup \left({\displaystyle {\cup }_{i=1}^{\lfloor \frac{h}{2}\rfloor }{D}_{2i}}\right)$ 。通过计算，$\left|R_1\right|=\lceil \frac{h}{2}\rceil \cdot \frac{m}{2}+\lfloor \frac{h}{2}\rfloor \cdot \left(\frac{m}{2}-1\right)=h\cdot \frac{m}{2}-\lfloor \frac{h}{2}\rfloor$ 。因此得到上界${\gamma }_I\left(E{G}_m^h\right)\le \left|R_1\right|=h\cdot \frac{m}{2}-\lfloor \frac{h}{2}\rfloor$ 。

下面证明集合$R_1$ 是$E{G}_m^h$ 的所有意大利支配集中具有最小的意大利支配数。

将$E{G}_m^h$ 划分为块$B_j\left(j=1,2,\cdots ,l\right)$ ，其中$l=\lfloor \frac{h}{2}\rfloor +1$ 。定义对于$j=1,2,\cdots ,l-1$ ，$B_j=C_m^{2j-1}{C}_m^{2j}\backslash \left\{u_{2j}\right\}$ ；对于$j=l$ ，当$h\equiv 0\left(\mathrm{mod}2\right)$ 时，则$B_l=\left\{u_h\right\}$ ；若$h\equiv 1\left(\mathrm{mod}2\right)$ ，则$B_l=C_m^h$ 。设$D$ 是$E{G}_m^h$ 的任意一个意大利支配集，对于块$B_j\left(j=1,2,\cdots ,l-1\right)$ ，它包含两个几乎完整的环，只缺少一个割点。任何意大利支配集要覆盖这两个环的所有顶点至少需要$2\cdot \frac{m}{2}-1=m-1$ 个顶点来覆盖，即有$\left|D\cap B_j\right|\ge m-1,j=1,2,\cdots ,l-1$ 。对于块$B_l$ ，即对于$j=l$ ，若$h\equiv 0\left(\mathrm{mod}2\right)$ ，则$B_l=\left\{u_h\right\}$ 为割点，但$u_h$ 是割点，也可能被其他顶点支配，因此$\left|D\cap B_l\right|\ge 0$ 。若$h\equiv 1\left(\mathrm{mod}2\right)$ ，则$B_l=C_m^h$ 是一个完整的环，因此$\left|D\cap B_l\right|\ge \frac{m}{2}$ 。所以有意大利支配数的最小值为：

${\gamma }_I\left(E{G}_m^h\right)\ge {\displaystyle \sum _{j=1}^{l-1}\left|D\cap B_j\right|}+\left|D\cap B_l\right|=\left(l-1\right)\left(m-1\right)+\{\begin{array}{l}0,h\equiv 0\left(\mathrm{mod}2\right)\\ \frac{m}{2},h\equiv 1\left(\mathrm{mod}2\right)\end{array}$

代入$l=\lfloor \frac{h}{2}\rfloor +1$ ，化简可得${\gamma }_I\left(E{G}_m^h\right)\ge h\cdot \frac{m}{2}-\lfloor \frac{h}{2}\rfloor$ 。

结合上述不等式，因此得到，${\gamma }_I\left(E{G}_m^h\right)=h\cdot \frac{m}{2}-\lfloor \frac{h}{2}\rfloor$ 。

图5给出了$m\equiv 0\left(\mathrm{mod}2\right)$ 的$E{G}_m^h$ 和相应的意大利支配集$R_r$ ，$r=0,1$ 的例子。

Figure 5. $E{G}_m^h$ whit $m\equiv 1\left(\mathrm{mod}2\right)$ and their corresponding Italian dominating sets $R_r,r=0,1$

图5. $m\equiv 0\left(\mathrm{mod}2\right)$ 的$E{G}_m^h$ 和相应的意大利支配集$R_r$ ，$r=0,1$

□

4. $G_m^h$ 的意大利支配数

本节将推广至一般的仙人掌链$G_m^h$ ，探讨其意大利支配数的递推关系和上下界：

命题4：设图$G$ 是m-仙人掌链$G_m^h$ ，其意大利支配数满足以下不等式：

${\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil -1\le {\gamma }_I\left(G_m^h\right)\le {\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil$ 。

证明：仙人掌链$G_m^h$ 可视为在$G_m^{h-1}$ 上添加一个$m$ 阶的环$C_m^h$ ，并通过割点$u_{h-1}$ 连接而成。首先证明右不等式${\gamma }_I\left(G_m^h\right)\le {\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil$ 。设$D_{h-1}$ 为$G_m^{h-1}$ 的一个最小意大利支配集，即$\left|D_{h-1}\right|={\gamma }_I\left(G_m^{h-1}\right)$ 。考虑新环$C_m^h$ ，若割点$u_{h-1}\in D_{h-1}$ ，则其可以部分支配$C_m^h$ ；通过构造一个支配数为$\lceil \frac{m}{2}\rceil$ 的意大利支配集$D_h^{*}$ ，可确保$C_m^h$ 被完全支配。令$D_h=D_{h-1}\cup D_h^{*}$ ，则$D_h$ 为$G_m^h$ 的意大利支配集，且满足$\left|D_h\right|\le \left|D_{h-1}\right|+\lceil \frac{m}{2}\rceil ={\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil$ 故右不等式得证。

然后证明左不等式${\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil -1\le {\gamma }_I\left(G_m^h\right)$ 。设$D_h$ 为$G_m^h$ 的最小意大利支配集。根据添加一个新环$C_m^h$ ，根据命题2及$G_m^h$ 割点的必要性可知，增量至少$\lceil \frac{m}{2}\rceil -1$ 。 □

进一步建立一般仙人掌链$G_m^h$ 的意大利支配数表达式：

定理2：设图$G_m^h$ $\left(h\ge 2\right)$ 是一个m-仙人掌链，其意大利支配数${\gamma }_I\left(G_m^h\right)$ 满足：

${\gamma }_I\left(G_m^h\right)={\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil -1$ (1)

或 ${\gamma }_I\left(G_m^{h+1}\right)={\gamma }_I\left(G_m^h\right)+\lceil \frac{m}{2}\rceil$ (2)

若$\left\{u_i:i=1,2,\cdots ,h-1\right\}\subset T_h$ ，即其中$T_n$ 为$G_m^h$ 的某一个最小意大利支配集，则为式子(1)，否则为式子(2)。

证明：情形1：当$m\equiv 1\left(\mathrm{mod}2\right)$ 时，设$T_h$ 为$G_m^h$ 的一个最小意大利支配集，由引理1可知，$\left\{u_i:i=1,2,\cdots ,h-1\right\}\subset T_h$ ，对于$T_h$ 与中间环、首环、尾环的交集分别为，$\left|T_h\cap \left(C_m^j\backslash \left\{u_{j-1},u_j\right\}\right)\right|\ge \lceil \frac{m}{2}\rceil -2$ ，$\forall j=2,\cdots ,h-1$ ，$\left|T_h\cap \left(C_m^1\backslash \left\{u_1\right\}\right)\right|\ge \lceil \frac{m}{2}\rceil -1$ ，和$\left|T_h\cap \left(C_m^h\backslash \left\{u_{h-1}\right\}\right)\right|\ge \lceil \frac{m}{2}\rceil -1$ 。另一方面，由命题2，$\left|T_h\cap C_m^j\right|\le \lceil \frac{m}{2}\rceil$ 对于任意$j=1,2,\cdots ,h$ 综合以上不等式，通过求和可得$\left|T_h\right|={\displaystyle \sum _{j=1}^h\left|T_h\cap C_m^j\right|}-\left(h-1\right)\le h\lceil \frac{m}{2}\rceil -\left(h-1\right)$ ，且该上界可达。因此，${\gamma }_I\left(G_m^h\right)=h\lceil \frac{m}{2}\rceil -\left(h-1\right)$ 。结合定理1的结论，可以得到${\gamma }_I\left(G_m^h\right)={\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil -1$ 。

情形2：当$m\equiv 0\left(\mathrm{mod}2\right)$ 时，图在$G_m^{h-1}$ 上新添加一个新环$C_m^h$ ，并通过割点$u_{h-1}$ 连接而成，令$\left\{u_{h-1}\right\}=C_m^{h-1}\cap C_m^h$ 。分为两种子情况：

子情形2.1：$\left\{u_{h-1}\right\}\in D_{h-1}$ 。此时顶点$u_{h-1}$ 可支配$C_m^h$ 中两个邻点，因此剩余$m-3$ 个顶点至多需要$\frac{m}{2}-1$ 个顶点支配。因此，$\left|D_h\right|\le \left|D_{h-1}\right|+\left(\frac{m}{2}-1\right)$ ，即${\gamma }_I\left(G\right)\le {\gamma }_I\left(G_m^{h-1}\right)+\frac{m}{2}-1$ 。通过构造可达该上界，所以等式成立。

子情形2.2：$\left\{u_{h-1}\right\}\notin D_{h-1}$ 。此时$u_{h-1}$ 由$C_m^{h-1}$ 中两个顶点支配，其自身无法提供支配能力。新环$C_m^h$ 需要完整的支配集，所有$\left|D_h\right|\le \left|D_{h-1}\right|+\frac{m}{2}$ ，即${\gamma }_I\left(G\right)\le {\gamma }_I\left(G_m^{h-1}\right)+\frac{m}{2}$ 。另一方面，由$\left|D_h\cap C_m^h\right|=\frac{m}{2}$ 可得，$\left|D_{h-1}\right|\le \left|D_h\right|-\frac{m}{2}$ ，因此$\left|D_h\right|=\left|D_{h-1}\right|+\frac{m}{2}$ ，${\gamma }_I\left(G_m^h\right)={\gamma }_I\left(G_m^{h-1}\right)+\frac{m}{2}$ 。若${\gamma }_I\left(G_m^h\right)={\gamma }_I\left(G_m^{h-1}\right)+\lceil \frac{m}{2}\rceil$ ，则$C_m^h$ 中至少有$m-2$ 个顶点被支配，有$\left\{u_{h-1}\right\}\notin D_{h-1}$ 。此时可选取$C_m^h$ 中的支配顶点使得$u_h\in D_h$ ，其中$\left\{u_h\right\}=C_m^h\cap C_m^{h+1}$ 此时转化为情况2.1，因此，${\gamma }_I\left(G_m^{h+1}\right)=\gamma \left(G_m^h\right)+\lceil \frac{m}{2}\rceil -1$ 。

综上，定理2得证。 □

由定理2易知：

推论3：设图$G$ 是等距仙人掌链。当$m\equiv 1\left(\mathrm{mod}2\right)$ 时，或者当$m\equiv 0\left(\mathrm{mod}2\right)$ 且$c\equiv 0\left(\mathrm{mod}2\right)$ 时，其意大利支配数为${\gamma }_I\left(G_m^h\right)=h\lceil \frac{m}{2}\rceil -h+1$ 。

定理3：设图$G_m^h$ 是任意的m-仙人掌链，其中$h\ge 2$ ，$m\ge 4$ ，则其意大利支配数${\gamma }_I\left(G_m^h\right)$ 满足不等式

$h\lceil \frac{m}{2}\rceil -\left(h-1\right)\le {\gamma }_I\left(G_m^h\right)\le h\lceil \frac{m}{2}\rceil -\lfloor \frac{h}{2}\rfloor$ 。

证明：不等式左端由定理2可以得到。

不等式右端通过构造一条极值链$G_m^h$ 实现依次添加环$C_m^j\left(j=2,\cdots ,h\right)$ ，并控制其与前序子链$G_m^{j-1}$ 的连接方式，使得满足意大利支配数。对于$j\equiv 0\left(\mathrm{mod}2\right)$ ，${\gamma }_I\left(G_m^j\right)={\gamma }_I\left(G_m^{j-1}\right)+\lceil \frac{m}{2}\rceil -1$ ；对于$j\equiv 1\left(\mathrm{mod}2\right)$ ，${\gamma }_I\left(G_m^j\right)={\gamma }_I\left(G_m^{j-1}\right)+\lceil \frac{m}{2}\rceil$ 。通过计算即得，${\gamma }_I\left(G_m^h\right)=\lceil \frac{m}{2}\rceil +{\displaystyle \sum _{j=2}^h{\Delta }_j}=h\lceil \frac{m}{2}\rceil -\lfloor \frac{h}{2}\rfloor$ ，其中${\Delta }_j\in \left\{\lceil \frac{m}{2}\rceil -1,\lceil \frac{m}{2}\rceil \right\}$ 为第$j$ 步增量。该构造可达上界。 □

定理3中这些界限的达到链的拓扑结构相关，如本文分析了等距仙人掌链$E{G}_m^h$ 精确的意大利支配数，达到下界时，环间通过短路径连接$c\equiv 0\left(\mathrm{mod}2\right)$ ，使得意大利支配集可复用割点，减少了支配点的需求。见图4；达到上界时，环间路径最长$c\equiv 1\left(\mathrm{mod}2\right)$ ，环间连接不对称，导致需更多独立支配点。增大总权重。见图5。总之，极值图的拓扑特征由参数$c$ 的奇偶控制的。

5. 总结

本文研究了一类等距仙人掌链的意大利支配数问题，通过结构分析与组合构造，给出了该图类意大利支配数的计算公式，建立了一般仙人掌链的上下界，其结果具有一般性和构造性。但在高维推广的情形尚未涉及，未来可进一步拓展至更复杂的网络结构。

基金项目

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

NOTES

^*通讯作者。