路径直积图的意大利控制数

摘要

研究了路径直积图P_n×P_m的意大利控制数。结合计算机构造证明和数学推导证明，确定了P_n×P₁、P_n×P₂和P_n×P₃的意大利控制数，并给出了P_n×P_m （m$\ge$4）意大利控制数的界。

关键词

意大利控制数; 直积; 路径

在图$G=(V,E)$中，$V$表示顶点的集合，$E$表示边的集合。顶点$v\in V$的开邻域是与$v$有边相连的顶点构成的集合，即$N(v)=\{u|u是顶点且(uv)\in E\}$。$N(v)$中包含的顶点的个数称为顶点$v$的度，记为$\mathrm{d}\mathrm{e}\mathrm{g}(v)$。图$G$的最小度和最大度分别记为$\delta$和$\Delta$。图$G$顶点的个数称为图$G$的阶。$P_n$表示阶为$n$的路径图。

图的罗马控制起源于古罗马帝国的军事防御问题^［1］。古罗马帝国的每个城市最多能安置2支军队驻守。对于没有军队驻守的城市，其相邻的城市中必须至少有一个城市安置2支军队驻守，以便在该城市受到侵犯时相邻的城市能派出1支军队来支援。在这种历史背景下产生了图的罗马控制，定义为：在图$G=(V,E)$中，$f$为从顶点集合$V$到数集$\{\mathrm{0,1},\mathrm{2}\}$的函数，如果每一个函数值为0的顶点$v$都至少与一个函数值为2的顶点相邻，则$f$为图$G$的罗马控制函数。$f$的权重$w(f)=\sum _{v\in V}f(v)$。图$G$的所有罗马控制函数权重的最小值称为图$G$的罗马控制数，记为${\gamma }_{\mathrm{R}}(G)$。关于罗马控制的相关研究结果可以参考文献［2-5］。

意大利控制^［6］是罗马控制的一种变形，也称为罗马｛2｝-控制^［7］或弱｛2｝-控制^［8］，定义为：设图$G=(V,E)$，函数f∶$V\to \{\mathrm{0,1},\mathrm{2}\}$，如果每一个函数值为0的顶点$v$都至少与一个函数值为2的顶点相邻或者至少与2个函数值为1的顶点相邻，那么$f$称为图$G$的意大利控制函数。$f$的权重$w(f)=\sum _{v\in V}f(v)$，权重的最小值称为图$G$的意大利控制数，记为${\gamma }_{\mathrm{I}}(G)$。若$f$满足$w(f)={\gamma }_{\mathrm{I}}(G)$，则称$f$为图$G$的${\gamma }_{\mathrm{I}}$-函数。

意大利控制是图的控制理论中较为活跃的研究课题，吸引了很多学者。文献［6］中研究了意大利控制数与罗马控制数、彩虹控制数、经典控制数的关系，并证明了任意图的意大利控制数都小于等于其2-彩虹控制数。文献［7］中研究了树图T的意大利控制数，确定了分别满足$\gamma (T)+\mathrm{1}={\gamma }_{\mathrm{I}}(T)$和$\mathrm{2}\gamma (T)={\gamma }_{\mathrm{I}}(T)$的树图的特点，其中$\gamma (T)$是树图的控制数。文献［8］中给出了圈$C_n$与$C_{\mathrm{5}}$的笛卡尔乘积$C_n\square C_{\mathrm{5}}$的意大利控制数下界，并确定了$C_n\square C_{\mathrm{3}}$和$C_n\square C_{\mathrm{4}}$意大利控制数的精确值。文献［9］中确定了广义彼得森图$P(n,\mathrm{3})$意大利控制数的精确值。文献［10］中研究了有向圈乘积图的意大利控制数。文献［11］中研究了有根乘积图的意大利控制数。学者们还研究了与意大利控制相关的全局意大利控制^［12］、独立意大利控制^［13］、完美意大利控制^［14-16］、符号意大利控制^［17］、全意大利控制^［18］、外独立意大利控制^［19］、限制意大利控制^［20］、安全意大利控制^［21］等。

直积图，也称为克罗内克乘积图，是一种重要的图类，在实际中应用广泛，如在计算机通信网络、多处理器管理等领域。文献［22-23］中分别研究了直积图上的经典控制和完美控制。对于给定的2个图$G$和$H$，它们的直积图$G\times H=(V,E)$，其中顶点的集合为$V(G\times H)=\{(u,v)|u\in V(G),v\in V(H)\}$，边的集合为$E(G\times H)=\{(u_{\mathrm{1}},v_{\mathrm{1}})(u_{\mathrm{2}},v_{\mathrm{2}})|u_{\mathrm{1}}{u}_{\mathrm{2}}\in E(G),v_{\mathrm{1}}{v}_{\mathrm{2}}\in E(H)\}$。

本研究中确定了$P_n\times P_{\mathrm{1}}$、$P_n\times P_{\mathrm{2}}$和$P_n\times P_{\mathrm{3}}$意大利控制数的精确值，并给出了$P_n\times P_m$$(m\ge \mathrm{4})$意大利控制数的界。

以下是与本研究相关的定理：

定理1  ^［7］    　若图$G$为路径图$P_n$，则${\gamma }_{\mathrm{I}}(G)=⌈\frac{n+\mathrm{1}}{\mathrm{2}}⌉$。

定理2  ^［7］    　若图$G$为连通图，则${\gamma }_{\mathrm{I}}(G)\ge \frac{\mathrm{2}|V(G)|}{\Delta (G)+\mathrm{2}}$。

1 P_n$\times$P₁和P_n$\times$P₂意大利控制数

$P_n\times P_{\mathrm{1}}$是n个孤立点，因此可知$P_n\times P_{\mathrm{1}}$的意大利控制数为n，即：

定理3  　对于任意的正整数$n\ge \mathrm{1}$， ${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{1}})=n$。

由于$P_n\times P_{\mathrm{2}}$与2条不相交的路径图$P_n$是同构的，因此${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{2}})=\mathrm{2}{\gamma }_{\mathrm{I}}(P_n)$。由定理1，可得以下定理：

定理4  　令$G=P_n\times P_{\mathrm{2}}$，则

$${\gamma }_{\mathrm{I}}(G)=\mathrm{2}⌈\frac{n+\mathrm{1}}{\mathrm{2}}⌉=\left\{\begin{array}{l}n+\mathrm{1},n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\\ n+\mathrm{2},n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})\end{array}\right.$$

2 P_n$\times$P₃意大利控制数

2.1　P_n$\times$P_m意大利控制数的上界

通过构造路径直积图的意大利控制函数可以得到${\gamma }_{\mathrm{I}}(P_n\times P_m)$$(m\ge \mathrm{3})$的上界。

定理5  　对于任意的正整数$m\ge \mathrm{3}$，$n\ge m$，$k\ge \mathrm{2}$， 有：

$${\gamma }_{\mathrm{I}}(P_n\times P_m)\le$$

$$\left\{\begin{array}{l}k(n+\mathrm{2}),m=\mathrm{3}k或m=\mathrm{3}k-\mathrm{1}\mathrm{且}\mathrm{n}\mathrm{为}\mathrm{偶}\mathrm{数}\\ k(n+\mathrm{2})-\mathrm{1},m=\mathrm{3}k-\mathrm{1}\mathrm{且}\mathrm{n}\mathrm{为}\mathrm{奇}\mathrm{数}\\ k(n+\mathrm{2})-\mathrm{4},m=\mathrm{3}k-\mathrm{2}\end{array}\right.$$

证明：设$G=P_n\times P_m$的顶点集合为$V=\{v_{i,j}|\mathrm{0}\le i\le n-\mathrm{1,0}\le j\le m-\mathrm{1}\}$，其中$i$是顶点的行标号，$j$是顶点的列标号。

（1） 当$m=\mathrm{3}k$时，按照下式构造意大利控制函数$f$：

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

图1显示了$P_{\mathrm{7}}\times P_{\mathrm{6}}$上的意大利控制函数$f$，其中$R_n(R_m)$表示随着$n(m)$的增长，重复相应的1行（3列）。图1中，空心圆圈表示$f(v_{i,j})=\mathrm{0}$的顶点，黑色实心点表示$f(v_{i,j})=\mathrm{1}$的顶点，较大的粗边空心圆圈表示$f(v_{i,j})=\mathrm{2}$的顶点。

图1  P₇$\times$P₆上的意大利控制函数f

Fig.1  Italian dominating function f on P₇$\times$P₆

（2） 当$m=\mathrm{3}k-\mathrm{1}$时，分2种情况构造意大利控制函数$f$。

当n为偶数时，

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

当n为奇数时，

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\le m-\mathrm{3},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\le m-\mathrm{3},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}),j=m-\mathrm{1},j=m-\mathrm{2}\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

图2显示了$P_{\mathrm{6}}\times P_{\mathrm{5}}$和$P_{\mathrm{7}}\times P_{\mathrm{5}}$上的意大利控制函数$f$，其中$R_n(R_m)$表示随着$n(m)$的增长，重复相应的2行（3列）。

图2  P₆$\times$P₅和P₇$\times$P₅上的意大利控制函数f

Fig.2  Italian dominating function f on P₆$\times$P₅ and P₇$\times$P₅

（3） 当$m=\mathrm{3}k-\mathrm{2}$时，分3种情况构造意大利控制函数$f$。

当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{2},j=m-\mathrm{3}\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{1},j=m-\mathrm{4}\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\le n-\mathrm{5},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{2},j=m-\mathrm{3}\mathrm{或}\\ i=n-\mathrm{2},i=n-\mathrm{3},j=m-\mathrm{2},j=m-\mathrm{3}\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\le n-\mathrm{5},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{1},j=m-\mathrm{4}\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$f(v_{i,j})=\left\{\begin{array}{l}\mathrm{2},i=\mathrm{1},i=n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\le n-\mathrm{9},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{2},j=m-\mathrm{3}\mathrm{或}\\ i=n-\mathrm{2},i=n-\mathrm{3},j=m-\mathrm{2},j=m-\mathrm{3}\mathrm{或}\mathrm{i}=n-\mathrm{6},i=n-\mathrm{7},j=m-\mathrm{2},j=m-\mathrm{3}\\ \mathrm{1},i\ne \mathrm{1},i\ne n-\mathrm{2},j\le m-\mathrm{5},j\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\mathrm{或}\mathrm{i}\le n-\mathrm{9},i\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),j=m-\mathrm{1},j=m-\mathrm{4}\\ \mathrm{0},\mathrm{其}\mathrm{他}\end{array}\right.$$

图3显示了$P_{\mathrm{9}}\times P_{\mathrm{7}}$、$P_{\mathrm{10}}\times P_{\mathrm{7}}$和$P_{\mathrm{14}}\times P_{\mathrm{7}}$上的意大利控制函数$f$，其中$R_n(R_m)$表示随着$n(m)$的增长，重复相应的3行（3列）。

图3  P₉$\times$P₇、P₁₀$\times$P₇和P₁₄$\times$P₇上的意大利控制函数f

Fig.3  Italian dominating function f on P₉$\times$P₇，P₁₀$\times$P₇ and P₁₄$\times$P₇

可以验证，按照以上方式构造的$f$均为意大利控制函数。根据$f$的定义并结合图示，可以计算得到$f$的权重，如下所示：

$$w(f)=\left\{\begin{array}{ll}\frac{m}{\mathrm{3}}(n+\mathrm{2})=\frac{mn+\mathrm{2}m}{\mathrm{3}},m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})& \\ \frac{m-\mathrm{4}}{\mathrm{3}}(n+\mathrm{2})+\mathrm{6}\frac{n}{\mathrm{3}}=\frac{mn+\mathrm{2}n+\mathrm{2}m-\mathrm{8}}{\mathrm{3}},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})& \\ \frac{m-\mathrm{4}}{\mathrm{3}}(n+\mathrm{2})+\mathrm{6}\frac{n-\mathrm{4}}{\mathrm{3}}+\mathrm{8}=\frac{mn+\mathrm{2}n+\mathrm{2}m-\mathrm{8}}{\mathrm{3}},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})& \\ \frac{m-\mathrm{4}}{\mathrm{3}}(n+\mathrm{2})+\mathrm{6}\frac{n-\mathrm{8}}{\mathrm{3}}+\mathrm{16}=\frac{mn+\mathrm{2}n+\mathrm{2}m-\mathrm{8}}{\mathrm{3}},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})& \\ \frac{m+\mathrm{1}}{\mathrm{3}}(n+\mathrm{2})=\frac{mn+\mathrm{2}m+n+\mathrm{2}}{\mathrm{3}},m\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})& \\ \frac{m-\mathrm{2}}{\mathrm{3}}(n+\mathrm{2})+\mathrm{2}\frac{n+\mathrm{1}}{\mathrm{2}}=\frac{mn+\mathrm{2}m+n-\mathrm{1}}{\mathrm{3}},m\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}),n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})& \end{array}\right.$$

因此，可得

$${\gamma }_{\mathrm{I}}(P_n\times P_m)\le w(f)=$$

$$\left\{\begin{array}{l}\frac{mn+\mathrm{2}m}{\mathrm{3}},m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \frac{mn+\mathrm{2}n+\mathrm{2}m-\mathrm{8}}{\mathrm{3}},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \frac{mn+n+\mathrm{2}m+\mathrm{2}}{\mathrm{3}}-\frac{\mathrm{1}-{(-\mathrm{1})}^n}{\mathrm{2}},m\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\end{array}\right.$$

即：

$${\gamma }_{\mathrm{I}}(P_n\times P_m)\le$$

$$\left\{\begin{array}{l}k(n+\mathrm{2}),m=\mathrm{3}k或m=\mathrm{3}k-\mathrm{1}\mathrm{且}\mathrm{n}\mathrm{为}\mathrm{偶}\mathrm{数}\\ k(n+\mathrm{2})-\mathrm{1},m=\mathrm{3}k-\mathrm{1}\mathrm{且}\mathrm{n}\mathrm{为}\mathrm{奇}\mathrm{数}\\ k(n+\mathrm{2})-\mathrm{4},m=\mathrm{3}k-\mathrm{2}\end{array}\right.$$

根据定理5，可以得到$P_n\times P_{\mathrm{3}}$意大利控制数的上界，即有以下的推论：

推论1  　对于任意的正整数$n\ge \mathrm{3}$， ${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{3}})\le n+\mathrm{2}$。

2.2　P_n$\times$P₃意大利控制数的下界

本节中证明$P_n\times P_{\mathrm{3}}$意大利控制数的下界也是$n+\mathrm{2}$。令$G=P_n\times P_{\mathrm{3}}$，顶点集$V(G)=\{v_{i,j}|\mathrm{0}\le i\le n-\mathrm{1,0}\le j\le \mathrm{2}\}$，$f$是$G$上的意大利控制函数，记$V^i=\{v_{i,j}|\mathrm{0}\le j\le \mathrm{2}\}$$(\mathrm{0}\le i\le n-\mathrm{1})$，$f_i=f(V^i)=\sum _{v_{i,j}\in V^i}f(v_{i,j})$。

引理1  　在图$P_n\times P_{\mathrm{3}}$中，若$f$为$P_n\times P_{\mathrm{3}}$的意大利控制函数，则以下结论均成立：

（1） 若$f_i=\mathrm{0}$$(\mathrm{1}\le i\le n-\mathrm{2})$，则$f_{i-\mathrm{1}}+f_{i+\mathrm{1}}\ge \mathrm{4}$。

（2） 若$f_{\mathrm{0}}=\mathrm{0}$，则$f_{\mathrm{1}}\ge \mathrm{4}$；若$f_{\mathrm{0}}=\mathrm{1}$，则$f_{\mathrm{1}}\ge \mathrm{2}$；若$f_{\mathrm{0}}=\mathrm{2}$，则$f_{\mathrm{1}}\ge \mathrm{2}$。若$f_{n-\mathrm{1}}=\mathrm{0}$，则$f_{n-\mathrm{2}}\ge \mathrm{4}$；若$f_{n-\mathrm{1}}=\mathrm{1}$，则$f_{n-\mathrm{2}}\ge \mathrm{2}$；若$f_{n-\mathrm{1}}=\mathrm{2}$，则$f_{n-\mathrm{2}}\ge \mathrm{2}$。

（3） $f_{\mathrm{0}}+f_{\mathrm{1}}\ge \mathrm{3}$；若$f_{\mathrm{0}}=\mathrm{1}$，$f_{\mathrm{1}}\le \mathrm{3}$，则$f_{\mathrm{2}}\ge \mathrm{1}$。$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}\ge \mathrm{3}$；若$f_{n-\mathrm{1}}=\mathrm{1}$，$f_{n-\mathrm{2}}\le \mathrm{3}$，则$f_{n-\mathrm{3}}\ge \mathrm{1}$。

（4） $f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}}\ge \mathrm{4}$，$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}+f_{n-\mathrm{3}}\ge \mathrm{4}$。

（5） $f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}}\ge \mathrm{3}$$(\mathrm{2}\le i\le n-\mathrm{3})$。

证明：（1） 若$f_i=\mathrm{0}$ $(\mathrm{1}\le i\le n-\mathrm{1})$，有$f(v_{i,\mathrm{0}})=f(v_{i,\mathrm{1}})=f(v_{i,\mathrm{2}})=\mathrm{0}$，则

$$\begin{array}{l}{f}_{i-\mathrm{1}}+f_{i+\mathrm{1}}={\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{2}}}f(v_{i-\mathrm{1},j})+{\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{2}}}f(v_{i+\mathrm{1},j})=(f(v_{i-\mathrm{1,0}})+f(v_{i-\mathrm{1,2}})+f(v_{i+\mathrm{1,0}})+\\ f(v_{i+\mathrm{1,2}}))+(f(v_{i-\mathrm{1,1}})+f(v_{i+\mathrm{1,1}}))\ge \mathrm{2}+\mathrm{2}=\mathrm{4}\end{array}$$

由$f_{i-\mathrm{1}}+f_{i+\mathrm{1}}\ge \mathrm{4}$可知，若$f_{i-\mathrm{1}}=\mathrm{0,1},\mathrm{2,3}$，则$f_{i+\mathrm{1}}\ge \mathrm{4,3},\mathrm{2,1}$；若$f_{i-\mathrm{1}}\ge \mathrm{4}$，则$f_{i+\mathrm{1}}\ge \mathrm{0}$。因此，$f_{i-\mathrm{1}}$和$f_{i+\mathrm{1}}$要么满足$f_{i-\mathrm{1}}=\mathrm{2}$且$f_{i+\mathrm{1}}\ge \mathrm{2}$，要么满足$f_{i-\mathrm{1}}\ge \mathrm{3}$或$f_{i+\mathrm{1}}\ge \mathrm{3}$。

（2） 若$f_{\mathrm{0}}=\mathrm{0}$，则

$$f_{\mathrm{1}}={\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{2}}}f(v_{\mathrm{1},j})=(f(v_{\mathrm{1,0}})+f(v_{\mathrm{1,2}}))+$$

$$f(v_{\mathrm{1,1}})\ge \mathrm{2}+\mathrm{2}=\mathrm{4}$$

若$f_{\mathrm{0}}=\mathrm{1}$，则$f(v_{\mathrm{0,0}})$和$f(v_{\mathrm{0,2}})$中至少有一个等于0，所以$f(v_{\mathrm{1,1}})=\mathrm{2}$，即$f_{\mathrm{1}}\ge \mathrm{2}$。若$f_{\mathrm{0}}=\mathrm{2}$，则$f(v_{\mathrm{0,0}})$、$f(v_{\mathrm{0,1}})$和$f(v_{\mathrm{0,2}})$中至少有一个等于0，所以有$f(v_{\mathrm{1,1}})=\mathrm{2}$或者$f(v_{\mathrm{1,0}})+f(v_{\mathrm{1,2}})\ge \mathrm{2}$，即有$f_{\mathrm{1}}\ge \mathrm{2}$。

同理可得，若$f_{n-\mathrm{1}}=\mathrm{0}$，则$f_{n-\mathrm{2}}\ge \mathrm{4}$；若$f_{n-\mathrm{1}}=\mathrm{1}$，则$f_{n-\mathrm{2}}\ge \mathrm{2}$；若$f_{n-\mathrm{1}}=\mathrm{2}$，则$f_{n-\mathrm{2}}\ge \mathrm{2}$。

（3） 当$f_{\mathrm{0}}\ge \mathrm{3}$时，显然有$f_{\mathrm{0}}+f_{\mathrm{1}}\ge \mathrm{3}$。当$f_{\mathrm{0}}<\mathrm{3}$时，由本引理第2条结论，即由（2）可知，$f_{\mathrm{0}}+f_{\mathrm{1}}\ge \mathrm{3}$，并且由（2）的证明可知，若$f_{\mathrm{0}}=\mathrm{1}$，则$f(v_{\mathrm{1,1}})=\mathrm{2}$。若$f_{\mathrm{1}}\le \mathrm{3}$，则$f(v_{\mathrm{1,0}})$和$f(v_{\mathrm{1,2}})$中至少有一个等于0。由于$f_{\mathrm{0}}=\mathrm{1}$，根据意大利控制函数的定义，$f_{\mathrm{2}}\ge \mathrm{1}$。

同理可得，$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}\ge \mathrm{3}$；若$f_{n-\mathrm{1}}=\mathrm{1}$，$f_{n-\mathrm{2}}\le \mathrm{3}$，则$f_{n-\mathrm{3}}\ge \mathrm{1}$。

（4） 根据本引理的（2）和（3），有$f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}}\ge \mathrm{4}$，$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}+f_{n-\mathrm{3}}\ge \mathrm{4}$。

（5） 若$f_i=\mathrm{0}$，由本引理（1）可知，$f_{i-\mathrm{1}}+f_{i+\mathrm{1}}\ge \mathrm{4}$，所以$f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}}\ge \mathrm{3}$。若$f_i=\mathrm{1}$或2，则$f(v_{i,\mathrm{0}})$、$f(v_{i,\mathrm{1}})$和$f(v_{i,\mathrm{2}})$中至少有一个为0，故$f(v_{i-\mathrm{1,1}})+f(v_{i+\mathrm{1,1}})\ge \mathrm{2}$或$f(v_{i-\mathrm{1,0}})+f(v_{i-\mathrm{1,2}})+f(v_{i+\mathrm{1,0}})+f(v_{i+\mathrm{1,2}})\ge \mathrm{2}$，故$f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}}\ge \mathrm{3}$。

定理6  　${\gamma }_{\mathrm{I}}(P_{\mathrm{3}}\times P_{\mathrm{3}})=\mathrm{4}$。

证明：在图$P_{\mathrm{3}}\times P_{\mathrm{3}}$中构造意大利控制函数$f$：$f(v_{\mathrm{1,0}})=f(v_{\mathrm{1,2}})=\mathrm{1}$，$f(v_{\mathrm{1,1}})=\mathrm{2}$，其他顶点$f(v_{i,j})=\mathrm{0}$。$f$为意大利控制函数且$f$的权重$w(f)=\mathrm{4}$，所以${\gamma }_{\mathrm{I}}(P_{\mathrm{3}}\times P_{\mathrm{3}})\le \mathrm{4}$。根据引理1（4）可知$f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}}\ge \mathrm{4}$，所以${\gamma }_{\mathrm{I}}(P_{\mathrm{3}}\times P_{\mathrm{3}})=\mathrm{4}$。

定理7  　对于任意的正整数$n\ge \mathrm{4}$， ${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{3}})\ge n+\mathrm{2}$。

证明：在图$G=P_n\times P_{\mathrm{3}}$中，顶点集合$V(G)=\{v_{i,j}|\mathrm{0}\le i\le n-\mathrm{1,0}\le j\le \mathrm{2}\}$，$V^i=\{v_{i,j}|\mathrm{0}\le j\le \mathrm{2}\}$

$(\mathrm{0}\le i\le n-\mathrm{1})$，$f$为$P_n\times P_{\mathrm{3}}$的${\gamma }_{\mathrm{I}}$-函数，$f_i=f(V^i)=\sum _{v_{i,j}\in V^i}f(v_{i,j})$。

由引理1（3）、（4）、（5）可知，$f_{\mathrm{0}}+f_{\mathrm{1}}\ge \mathrm{3}$，$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}\ge \mathrm{3}$，$f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}}\ge \mathrm{4}$，$f_{n-\mathrm{1}}+f_{n-\mathrm{2}}+f_{n-\mathrm{3}}\ge \mathrm{4}$，$f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}}\ge \mathrm{3}$$(\mathrm{2}\le i\le n-\mathrm{3})$。

当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$w(f)={\displaystyle \sum _{i=\mathrm{0}}^{n-\mathrm{1}}}{f}_i=(f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}})+{\displaystyle \sum _{i=\mathrm{4}}^{n-\mathrm{5}}}(f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}})+(f_{n-\mathrm{3}}+f_{n-\mathrm{2}}+f_{n-\mathrm{1}})\ge \mathrm{4}+\frac{\mathrm{3}(n-\mathrm{6})}{\mathrm{3}}+\mathrm{4}=n+\mathrm{2}$$

当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$w(f)={\displaystyle \sum _{i=\mathrm{0}}^{n-\mathrm{1}}}{f}_i=(f_{\mathrm{0}}+f_{\mathrm{1}})+{\displaystyle \sum _{i=\mathrm{3}}^{n-\mathrm{4}}}(f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}})+(f_{n-\mathrm{2}}+f_{n-\mathrm{1}})\ge \mathrm{3}+\frac{\mathrm{3}(n-\mathrm{4})}{\mathrm{3}}+\mathrm{3}=n+\mathrm{2}$$

当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})$时，

$$w(f)={\displaystyle \sum _{i=\mathrm{0}}^{n-\mathrm{1}}}{f}_i=(f_{\mathrm{0}}+f_{\mathrm{1}}+f_{\mathrm{2}})+{\displaystyle \sum _{i=\mathrm{4}}^{n-\mathrm{5}}}(f_{i-\mathrm{1}}+f_i+f_{i+\mathrm{1}})+(f_{n-\mathrm{2}}+f_{n-\mathrm{1}})\ge \mathrm{4}+\frac{\mathrm{3}(n-\mathrm{5})}{\mathrm{3}}+\mathrm{3}=n+\mathrm{2}$$

综上，${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{3}})\ge n+\mathrm{2}$。

由推论1和定理7，可以得到以下定理：

定理8  　对于任意的正整数$n\ge \mathrm{4}$， ${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{3}})=n+\mathrm{2}$。

3 P_n$\times$P_m（m$\ge$4）意大利控制数的界

由于$\Delta (P_n\times P_m)=\mathrm{4}$且$\left|V(G)\right|=mn$，因此根据定理2可以得到推论2。

推论2  　若$G=P_n\times P_m$，则${\gamma }_{\mathrm{I}}(G)\ge \frac{mn}{\mathrm{3}}$。

由定理5和推论2可以得到定理9。

定理9  　对于任意的正整数$m\ge \mathrm{4}$且$n\ge m$，有：

$$\frac{mn}{\mathrm{3}}\le {\gamma }_{\mathrm{I}}(P_n\times P_m)\le$$

$$\left\{\begin{array}{l}\frac{mn+\mathrm{2}m}{\mathrm{3}},m\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \frac{mn+\mathrm{2}n+\mathrm{2}m-\mathrm{8}}{\mathrm{3}},m\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\\ \frac{mn+n+\mathrm{2}m+\mathrm{2}}{\mathrm{3}}-\frac{\mathrm{1}-{(-\mathrm{1})}^n}{\mathrm{2}},m\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3})\end{array}\right.$$

4 结语

研究了路径直积图$P_n\times P_m$的意大利控制数，确定了一些路径直积图的意大利控制数， ${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{1}})=n$；当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{2}})=n+\mathrm{1}$；当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{2}})=n+\mathrm{2}$；${\gamma }_{\mathrm{I}}(P_{\mathrm{3}}\times P_{\mathrm{3}})=\mathrm{4}$；${\gamma }_{\mathrm{I}}(P_n\times P_{\mathrm{3}})=n+\mathrm{2}$$(n\ge \mathrm{4})$。对于$m,n\ge$$\mathrm{4}$，利用可递推的方法构造了$P_n\times P_m$的意大利控制函数，从而给出了${\gamma }_{\mathrm{I}}(P_n\times P_m)$的界。这种可递推的方法可以用于有任意多顶点的图类，实现用有限的方法解决无限的问题。

作者贡献声明

高 红：证明方法提出，算法总体设计，论文定稿。

黄佳欢：论文写作，画图，程序编写。

栗 坤：论文初稿的写作，程序调试。

杨元生：方法指导，程序设计指导。