广义Petersen图

摘要

在图G=（V， E）中，f为从顶点集合V到｛0，1，2｝的映射，如果满足所有 f（v）=0的顶点v其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点，则 f 称为图G的意大利控制函数。图G中所有顶点的函数值之和为f 的权重。权重的最小值为图G的意大利控制数。确定图的意大利控制数是NP （non‒deterministic polynomial） 困难的。通过构造可递推的意大利控制函数，计算出广义Petersen图P（n，1）和P（n，2）意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n，1）和P（n，2）意大利控制数的下界。最终确定了P（n，1）和P（n，2）意大利控制数的精确值。

关键词

图的控制; 意大利控制数; Petersen图

G=（V， E）表示一个图，顶点集合为V，边的集合为E。顶点v的开邻域为$N(v)=\{u\left|(u,v)\in E(G)\right.\}$，闭邻域为$N[v]=N(v)\bigcup \{v\}$。顶点v的度是N（v）中包含的顶点的个数，即$\mathrm{d}\mathrm{e}\mathrm{g}(v)=|N(v)|$。图G的最大度和最小度分别记作$\mathrm{\Delta }(G)$和$\mathrm{\delta }(G)$。若对于任意的$v\in V$，都有$\mathrm{d}\mathrm{e}\mathrm{g}(v)=r$，则图G称为r‒正则图。

在图G=（V， E）中，若$D\subseteq V(G)$且$N[D]=V(G)$，则称D为G的一个控制集。控制集包含元素个数的最小值称为图G的控制数，记为$\gamma (G)$。图的控制有很多种类型，其中意大利控制^［1］是一种新兴的控制类型，又称为罗马｛2｝‒控制^［2］或弱｛2｝‒控制^［3］。设$f:V\to \left\{\mathrm{0,1},\mathrm{2}\right\}$为图G上的函数，如果所有满足$f(v)=\mathrm{0}$的顶点$v$在其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点，那么函数$f$称为图G的意大利控制函数。意大利控制函数的权重等于图G中所有顶点的函数值之和，权重的最小值为图G的意大利控制数，记为${\gamma }_I(G)$。若$f$为图G的意大利控制函数并且$w(f)={\gamma }_I(G)$，则 $f$称为${\gamma }_I$‒function。若图G满足$\mathrm{2}\gamma \left(G\right)={\gamma }_I\left(G\right)$，则称图G为意大利图。关于意大利控制的研究可以参考文献［4-10］。

本文研究了广义Petersen图P（n，1）和P（n，2）意大利控制数。通过构造可递推的意大利控制函数计算出意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n，1）和P（n，2）意大利控制数的下界。最终确定了P（n，1）和P（n，2）意大利控制数的精确值。

1 P(n,1)的意大利控制数

1.1　P（n，1）意大利控制数的上界

广义Petersen图P（n， k）是3正则图，有2n个顶点。图1a和1b显示的是P（6，1）和P（6，2）。为了便于表示Petersen图的意大利控制函数，本文将P（n， k）表示为剪开的形式，图1c和1d显示的是P（6，1）和P（6，2）的剪开图。

图1 Petersen 图 P(6,1)和P(6,2)

Fig. 1 Petersen graph P(6,1) and P(6,2)

设G=P（n， k），f为图G上的意大利控制函数，则有下面的形式：

$$f(V(G))=\left(\begin{array}{ccccc}f(v_{\mathrm{0}})& f(v_{\mathrm{2}})& f(v_{\mathrm{4}})& \cdots & f(v_{\mathrm{2}n-\mathrm{2}})\\ f(v_{\mathrm{1}})& f(v_{\mathrm{3}})& f(v_{\mathrm{5}})& \cdots & f(v_{\mathrm{2}n-\mathrm{1}})\end{array}\right)$$

定理1   ${\gamma }_I(P(n,\mathrm{1}))\le n$。

证明：令G=P（n，1），在图G上构造意大利控制函数如下：

当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，$f(V(G))={\left(\begin{array}{c}\mathrm{10}\\ \mathrm{01}\end{array}\right)}^{\frac{n}{\mathrm{2}}}$；当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，$f(V(G))={\left(\begin{array}{c}\mathrm{10}\\ \mathrm{01}\end{array}\right)}^{\frac{n-\mathrm{1}}{\mathrm{2}}}\left(\begin{array}{c}\mathrm{1}\\ \mathrm{0}\end{array}\right)$。其中的$\frac{n}{\mathrm{2}}$和$\frac{n-\mathrm{1}}{\mathrm{2}}$表示将括号内的两列重复$\frac{n}{\mathrm{2}}$和$\frac{n-\mathrm{1}}{\mathrm{2}}$次。f的权重为：当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，$w(f)=\mathrm{2}\times \frac{n}{\mathrm{2}}=n$；当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，$w(f)=\mathrm{2}\times \frac{n-\mathrm{1}}{\mathrm{2}}+\mathrm{1}=n$。因此，${\gamma }_I(P(n,\mathrm{1}))\le w(f)=n$。

1.2　P（n，1）意大利控制数的下界

下面用袋装法证明P（n，1）意大利控制数的下界也是n。令f是P（n，1）上的意大利控制函数，记$w(f_i)=f(v_{\mathrm{2}i})+f(v_{\mathrm{2}i+\mathrm{1}})$，$V^i=\{v_{\mathrm{2}i},v_{\mathrm{2}i+\mathrm{1}}\}$，$\mathrm{0}\le i\le n-\mathrm{1}$。

引理1   如果$w(f_i)=\mathrm{0}$（$\mathrm{0}\le i\le n-\mathrm{1}$），则$w(f_{i-\mathrm{1}})+w(f_{i+\mathrm{1}})\ge \mathrm{4}$，下标对2n取模。

证明：因为$w(f_i)=\mathrm{0}$，即$f(v_{\mathrm{2}i})=f(v_{\mathrm{2}i+\mathrm{1}})=\mathrm{0}$，根据意大利控制函数的定义，可知$f(v_{\mathrm{2}i-\mathrm{2}})+f(v_{\mathrm{2}i+\mathrm{2}})\ge \mathrm{2}$且$f(v_{\mathrm{2}i-\mathrm{1}})+f(v_{\mathrm{2}i+\mathrm{3}})\ge \mathrm{2}$。因此，

$$\begin{array}{l}w(f_{i-\mathrm{1}})+w(f_{i+\mathrm{1}})=\\ f(v_{\mathrm{2}i-\mathrm{2}})+f(v_{\mathrm{2}i-\mathrm{1}})+f(v_{\mathrm{2}i+\mathrm{2}})+f(v_{\mathrm{2}i+\mathrm{3}})=\\ f(v_{\mathrm{2}i-\mathrm{2}})+f(v_{\mathrm{2}i+\mathrm{2}})+f(v_{\mathrm{2}i-\mathrm{1}})+f(v_{\mathrm{2}i+\mathrm{3}})\ge \\ \mathrm{2}+\mathrm{2}=\mathrm{4}\end{array}$$

定理2   ${\gamma }_I(P(n,\mathrm{1}))\ge n$。

证明：令G=P（n，1），通过下面的步骤将G的顶点装入B₁、B₂、B₃、B₄、B₅五个集合（袋子）中。

令B₁ =B₂ =B₃ =B₄ =B₅ = $\varphi$， m₁= m₂= m₃= m₄= m₅=0，D［i］=0 （$\mathrm{0}\le i\le n-\mathrm{1}$）。

第1步：对所有满足$w(f_i)=\mathrm{0}\wedge w(f_{i+\mathrm{1}})=\mathrm{2}$的i，将$V^i$和$V^{i+\mathrm{1}}$装入$B_{\mathrm{1}}$，即$B_{\mathrm{1}}=B_{\mathrm{1}}\bigcup V^i\bigcup V^{i+\mathrm{1}}$，并且$m_{\mathrm{1}}=m_{\mathrm{1}}+\mathrm{1}$，$D[i]=D[i+\mathrm{1}]=\mathrm{1}$。这里“$\wedge$”表示“并且”。

第2步：对有满足$w(f_i)=\mathrm{0}\wedge w(f_{i+\mathrm{1}})\ge \mathrm{3}\wedge w(f_{i+\mathrm{2}})=\mathrm{0}\wedge D[i+\mathrm{2}]=\mathrm{0}$的i，将$V^i$，$V^{i+\mathrm{1}}$和$V^{i+\mathrm{2}}$装入$B_{\mathrm{2}}$，即$B_{\mathrm{2}}=B_{\mathrm{2}}\bigcup V^i\bigcup V^{i+\mathrm{1}}\bigcup V^{i+\mathrm{2}}$，并且$m_{\mathrm{2}}=m_{\mathrm{2}}+\mathrm{1}$，$D[i]=D[i+\mathrm{1}]=D[i+\mathrm{2}]=\mathrm{1}$。

第3步：对所有满足$w(f_i)=\mathrm{0}\wedge w(f_{i+\mathrm{1}})\ge \mathrm{3}\wedge (w(f_{i+\mathrm{2}})\ge \mathrm{1}\vee D[i+\mathrm{2}]=\mathrm{1})$的i，将$V^i$和$V^{i+\mathrm{1}}$装入$B_{\mathrm{3}}$，即$B_{\mathrm{3}}=B_{\mathrm{3}}\bigcup V^i\bigcup V^{i+\mathrm{1}}$，并且$m_{\mathrm{3}}=m_{\mathrm{3}}+\mathrm{1}$，$D[i]=D[i+\mathrm{1}]=\mathrm{1}$。

第4步：所有满足$w(f_i)=\mathrm{0}\wedge w(f_{i+\mathrm{1}})\le \mathrm{1}$的i，由引理1知，$w(f_{i-\mathrm{1}})\ge \mathrm{3}$，将$V^{i-\mathrm{1}}$和$V^i$装入$B_{\mathrm{4}}$，即$B_{\mathrm{4}}=B_{\mathrm{4}}\bigcup V^{i-\mathrm{1}}\bigcup V^i$，并且$m_{\mathrm{4}}=m_{\mathrm{4}}+\mathrm{1}$，$D[i-\mathrm{1}]=D[i]=\mathrm{1}$。

经过以上步骤，对于所有满足$D[i]=\mathrm{0}$的$i$，都有$w(f_i)>\mathrm{0}$。

令$B_{\mathrm{5}}=V(G)-B_{\mathrm{1}}-B_{\mathrm{2}}-B_{\mathrm{3}}-B_{\mathrm{4}}$，$m_{\mathrm{5}}=\frac{|B_{\mathrm{5}}|}{\mathrm{2}}$。因为$\mathrm{2}{m}_{\mathrm{1}}+\mathrm{3}{m}_{\mathrm{2}}+\mathrm{2}{m}_{\mathrm{3}}+\mathrm{2}{m}_{\mathrm{4}}+m_{\mathrm{5}}=n$，所以

$$\begin{array}{l}f(V(G))\ge \\ \mathrm{2}{m}_{\mathrm{1}}+\mathrm{3}{m}_{\mathrm{2}}+\mathrm{3}{m}_{\mathrm{3}}+\mathrm{3}{m}_{\mathrm{4}}+m_{\mathrm{5}}\ge \\ \mathrm{2}{m}_{\mathrm{1}}+\mathrm{3}{m}_{\mathrm{2}}+\mathrm{2}{m}_{\mathrm{3}}+\mathrm{2}{m}_{\mathrm{4}}+m_{\mathrm{5}}=\\ n\end{array}$$

综上可得，${\gamma }_I(P(n,\mathrm{1}))\ge n$。

根据定理1和定理2，可以得到定理3。

定理3   对任意的正整数$n\ge \mathrm{3}$，${\gamma }_I(P(n,\mathrm{1}))=n$。

1.3　P（n，1）意大利控制数与2-彩虹控制数和经典控制数的关系

定理4  ^［11］     对任意的正整数$n\ge \mathrm{5}$，${\gamma }_{r\mathrm{2}}(P(n,\mathrm{1}))\ge n$，其中${\gamma }_{r\mathrm{2}}$表示2‒彩虹控制数。

由定理3和定理4可以得到定理5。

定理5   ${\gamma }_I(P(n,\mathrm{1}))={\gamma }_{r\mathrm{2}}(P(n,\mathrm{1}))$。

定理6 ^［12］     对任意的正整数$n\ge \mathrm{3}$，当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，$\gamma (P(n,\mathrm{1}))=\frac{n}{\mathrm{2}}+\mathrm{1}$；当$n\equiv \mathrm{0,1},\mathrm{3}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，$\gamma (P(n,\mathrm{1}))=⌈\frac{n}{\mathrm{2}}⌉$。

根据定理3和定理6，可以得到定理7。

定理7  当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，${\gamma }_I(P(n,\mathrm{1}))=\mathrm{2}\gamma (P(n,\mathrm{1}))$；当$n\cancel{\equiv }\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，${\gamma }_I(P(n,\mathrm{1}))\ne$ $\mathrm{2}\gamma (P(n,\mathrm{1}))$。因此，当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，P（n，1）是意大利图；当$n\cancel{\equiv }\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，P（n，1）不是意大利图。

2 P(n,2)的意大利控制数

2.1　P（n，2）意大利控制数的上界

定理8  ^［2］     对于任意的图G， ${\gamma }_I(G)\le {\gamma }_{r\mathrm{2}}(G)$，其中${\gamma }_{r\mathrm{2}}(G)$表示2‒彩虹控制数。

定 理9^［13］ 当$n\equiv \mathrm{0,3},\mathrm{4,9}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$；否则，${\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。

定理10   当$n\equiv \mathrm{0,3},\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))\le ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$；当$n\equiv \mathrm{1,2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))\le ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。

证明：根据定理2和定理3，可以得到当$n\equiv \mathrm{0},$$\mathrm{3,4},\mathrm{9}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))\le {\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$。当$n\equiv \mathrm{1,2},\mathrm{6,7}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))\le {\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。

当$n\equiv \mathrm{5,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，通过构造可递推的意大利控制函数可以证明${\gamma }_I(P(n,\mathrm{2}))$的上界是$⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$而不是$⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。当$n\equiv \mathrm{5}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，构造$f(V(G))={\left(\begin{array}{c}\mathrm{01001}\\ \mathrm{00110}\end{array}\right)}^{\frac{n}{\mathrm{5}}}$，则$w(f)=\frac{n}{\mathrm{5}}\times \mathrm{4}=\frac{\mathrm{4}n}{\mathrm{5}}$。当$n\equiv \mathrm{8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，构造$f(V(G))={\left(\begin{array}{c}\mathrm{01001}\\ \mathrm{00110}\end{array}\right)}^{\frac{n}{\mathrm{5}}}\left(\begin{array}{c}\mathrm{001}\\ \mathrm{110}\end{array}\right)$，则$w(f)=\frac{n-\mathrm{3}}{\mathrm{5}}\times \mathrm{4}+\mathrm{3}=\frac{\mathrm{4}n+\mathrm{3}}{\mathrm{5}}$。因此，当$n\equiv \mathrm{5,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))\le ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$。

综上，定理成立。

2.2　P（n，2）意大利控制数的下界

定理11  ^［2］     若G为连通图且最大度$\mathrm{\Delta }(G)=\Delta$，则${\gamma }_I(G)\ge \frac{\mathrm{2}\left|V(G)\right|}{\Delta +\mathrm{2}}$。

设$P(n,\mathrm{2})=(V,E)$，f为$P(n,\mathrm{2})$的意大利控制函数，$V_i=\left\{v\in V\left|f(v)=i,i=\mathrm{0,1},\mathrm{2}\right.\right\}$，则f也可表示为$f=(V_{\mathrm{0}},V_{\mathrm{1}},V_{\mathrm{2}})$，${\gamma }_I(P(n,\mathrm{2}))=w(f)=\sum _{v\in V}f(v)=\left|\left.V_{\mathrm{1}}\right|\right.+\mathrm{2}\left|\left.V_{\mathrm{2}}\right|\right.$。

定义1  设$f=(V_{\mathrm{0}},V_{\mathrm{1}},V_{\mathrm{2}})$为$P(n,\mathrm{2})$的${\gamma }_I$‒function，则控制代价函数$g_f$和剩余代价函数$r_f$分别定义为

当$v\in V_{\mathrm{0}}$时，$g_f(v)=\mathrm{0.2}\left|\left.V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|\left.V_{\mathrm{2}}\bigcap N(v)\right|\right.\right.$；

当$v\in V_{\mathrm{1}}$时，$g_f(v)=\mathrm{0.4}+\mathrm{0.2}\left|\left.V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|\left.V_{\mathrm{2}}\bigcap N(v)\right|\right.\right.$；

当$v\in V_{\mathrm{2}}$时，$g_f(v)=\mathrm{0.5}+\mathrm{0.2}\left|\left.V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|\left.V_{\mathrm{2}}\bigcap N(v)\right|\right.\right.$；$r_f(v)=g_f(v)-\mathrm{0.4}$；$g_f(V)=\sum _{v\in V}{g}_f(v)$；$r_f(V)=\sum _{v\in V}{r}_f(v)=\sum _{v\in V}(g_f(v)-\mathrm{0.4})$。

根据$g_f(v)$的定义（见定义1）和意大利控制函数的定义，可以得到下面的命题。

命题1   对于任意的顶点$v\in V$都有$g_f(v)\ge \mathrm{0.4}$。

设$E_{\mathrm{11}}=\{(u,v)\in E\left|u,v\in V_{\mathrm{1}}\right.\}$，$E_{\mathrm{12}}=\{(u,v)\in E\left|u\in V_{\mathrm{1}},v\in V_{\mathrm{2}}\right.\}$，根据$r_f(V)$的定义（见定义1）及意大利控制函数的定义，则命题2~8成立。

命题2   若存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\mathrm{2}$，则$r_f(V)\ge \mathrm{0}$。

命题3   若存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，则$r_f(V)\ge \mathrm{0.2}$。

命题4   若存在$v\in V_{\mathrm{2}}$，则$r_f(V)\ge \mathrm{0.4}$。

命题5   若存在$(u,v)\in E_{\mathrm{11}}$，则$r_f(V)\ge \mathrm{0.4}$。

命题6  若存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\left|N(v)\bigcap V_{\mathrm{2}}\right|=\mathrm{1}$，则$r_f(V)\ge \mathrm{0.6}$。

命题7   若存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\mathrm{2}$且$\left|N(v)\bigcap V_{\mathrm{2}}\right|=\mathrm{1}$，则$r_f(V)\ge \mathrm{0.8}$。

命题8   若存在$(u,v)\in E_{\mathrm{12}}$，则$r_f(V)\ge \mathrm{1}$。

命题2~8的示意图见图2a~2g，图中括号外的数字表示顶点的函数值$f(v)$，括号内的数字表示$g_f(v)$的值。

图2 命题2~8的示意图

Fig. 2 Sketches for propositions 2 to 8

定理12   设$f=(V_{\mathrm{0}},V_{\mathrm{1}},V_{\mathrm{2}})$为$P(n,\mathrm{2})$的${\gamma }_I$‒function，如果$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，那么${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$等价于$r_f(V)>\mathrm{0.2}$。如果$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，那么${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$等价于$r_f(V)>\mathrm{0.4}$。

证明：首先证明$g_f(V)={\gamma }_I(P(n,\mathrm{2}))$。实际上，

$$\begin{array}{l}{g}_f(V)=\\ \sum _{v\in V}{g}_f(v)=\\ \sum _{v\in V_{\mathrm{0}}}{g}_f(v)+\sum _{v\in V_{\mathrm{1}}}{g}_f(v)+\sum _{v\in V_{\mathrm{2}}}{g}_f(v)=\\ \sum _{v\in V_{\mathrm{0}}}(\mathrm{0.2}\left|V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|V_{\mathrm{2}}\bigcap N(v)\right|)+\\ \sum _{v\in V_{\mathrm{1}}}(\mathrm{0.4}+\mathrm{0.2}\left|V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|V_{\mathrm{2}}\bigcap N(v)\right|)+\\ \sum _{v\in V_{\mathrm{2}}}(\mathrm{0.5}+\mathrm{0.2}\left|V_{\mathrm{1}}\bigcap N(v)\right|+\mathrm{0.5}\left|V_{\mathrm{2}}\bigcap N(v)\right|)=\\ \mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{0}}\right|+\mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{0}}\right|+\\ \mathrm{0.4}\left|V_{\mathrm{1}}\right|+\mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{1}}\right|+\\ \mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{1}}\right|+\mathrm{0.5}\left|V_{\mathrm{2}}\right|+\\ \mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{2}}\right|+\mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{2}}\right|=\\ \mathrm{0.4}\left|V_{\mathrm{1}}\right|+\mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{0}}\right|+\\ \mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{1}}\right|+\mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\bigcap V_{\mathrm{2}}\right|+\\ \mathrm{0.5}\left|V_{\mathrm{2}}\right|+\mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{0}}\right|+\\ \mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{1}}\right|+\mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\bigcap V_{\mathrm{2}}\right|=\\ \mathrm{0.4}\left|V_{\mathrm{1}}\right|+\mathrm{0.2}\sum _{v\in V_{\mathrm{1}}}\left|N(v)\right|+\\ \mathrm{0.5}\left|V_{\mathrm{2}}\right|+\mathrm{0.5}\sum _{v\in V_{\mathrm{2}}}\left|N(v)\right|=\\ \mathrm{0.4}\left|V_{\mathrm{1}}\right|+\mathrm{0.2}\times \mathrm{3}\left|V_{\mathrm{1}}\right|+\mathrm{0.5}\left|V_{\mathrm{2}}\right|+\mathrm{0.5}\times \mathrm{3}\left|V_{\mathrm{2}}\right|=\\ \left|V_{\mathrm{1}}\right|+\mathrm{2}\left|V_{\mathrm{2}}\right|=\\ {\gamma }_I(P(n,\mathrm{2}))\end{array}$$

由$r_f(V)$的定义（见定义1）知，$r_f(V)=\sum _{v\in V}(g_f(v)-\mathrm{0.4})=g_f(V)-\mathrm{0.8}n$。再根据$g_f(V)={\gamma }_I(P(n,\mathrm{2}))$，有$r_f(V)={\gamma }_I(P(n,\mathrm{2}))-\mathrm{0.8}n$，即${\gamma }_I(P(n,\mathrm{2}))=r_f(V)+\mathrm{0.8}n$。从而可得

$${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉\iff r_f(V)>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉-\mathrm{0.8}n$$

如果$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{1}$，则$⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉-\mathrm{0.8}n=⌈\frac{\mathrm{4}(\mathrm{5}q+\mathrm{1})}{\mathrm{5}}⌉-\frac{\mathrm{4}(\mathrm{5}q+\mathrm{1})}{\mathrm{5}}$$=\mathrm{4}q+\mathrm{1}-\mathrm{4}q-\frac{\mathrm{4}}{\mathrm{5}}=\mathrm{0.2}$。

如果$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{2}$，则$⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉-\mathrm{0.8}n=⌈\frac{\mathrm{4}(\mathrm{5}q+\mathrm{2})}{\mathrm{5}}⌉-\frac{\mathrm{4}(\mathrm{5}q+\mathrm{2})}{\mathrm{5}}$$=\mathrm{4}q+\mathrm{2}-\mathrm{4}q-\frac{\mathrm{8}}{\mathrm{5}}=\mathrm{0.4}$。

所以，当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$等价于$r_f(V)>\mathrm{0.2}$。当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$等价于$r_f(V)>\mathrm{0.4}$。

定理13  令$G=P(n,\mathrm{2})=(V,E)$，则当$n\equiv \mathrm{0,3},\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(G)\ge ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$；当$n\equiv \mathrm{1,2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(G)\ge ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。

证明：设$f=(V_{\mathrm{0}},V_{\mathrm{1}},V_{\mathrm{2}})$为$P(n,\mathrm{2})$的${\gamma }_I$‒function。

情况1   当$n\equiv \mathrm{0,3},\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，由$G=P(n,\mathrm{2})$可知，$\mathrm{\Delta }(G)=\mathrm{3}$且$\left|V(G)\right|=\mathrm{2}n$。根据定理11，可得${\gamma }_I(P(n,\mathrm{2}))\ge ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$。

情况2   若$n\equiv \mathrm{1,2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，欲证${\gamma }_I(P(n,\mathrm{2}))\ge ⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$，即证${\gamma }_I(P(n,\mathrm{2}))>⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$。由定理12可知，只需证明：当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(V)>\mathrm{0.2}$；当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，$r_f(V)>\mathrm{0.4}$。

情形（1） $\left|V_{\mathrm{2}}\right|\ge \mathrm{2}$。若$\left|V_{\mathrm{2}}\right|\ge \mathrm{2}$，则由命题4可知，$r_f(V)\ge \mathrm{0.8}>\mathrm{0.4}>\mathrm{0.2}$。

情形（2） $\left|E_{\mathrm{11}}\right|\ge \mathrm{2}$。若$\left|E_{\mathrm{11}}\right|\ge \mathrm{2}$，则由命题5可知，$r_f(V)\ge \mathrm{0.8}>\mathrm{0.4}>\mathrm{0.2}$。

情形（3） $\left|V_{\mathrm{2}}\right|+\left|E_{\mathrm{11}}\right|\ge \mathrm{2}$。若$\left|V_{\mathrm{2}}\right|+$$\left|E_{\mathrm{11}}\right|\ge$$\mathrm{2}$，则由命题4~5可知，$r_f(V)\ge \mathrm{0.8}>\mathrm{0.4}>\mathrm{0.2}$。

情形（4） $\left|E_{\mathrm{12}}\right|\ge \mathrm{1}$。若$\left|E_{\mathrm{12}}\right|\ge \mathrm{1}$，则由命题8可知，$r_f(V)\ge \mathrm{1}>\mathrm{0.4}>\mathrm{0.2}$。

情形（5） 存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|\ge \mathrm{1}$且$\left|N(v)\bigcap V_{\mathrm{2}}\right|=\mathrm{1}$。这种情况由命题6~7可知，$r_f(V)\ge \mathrm{0.6}>\mathrm{0.4}>\mathrm{0.2}$。

综上，情形（1）~（5）证明完毕。

情形（6） $\left|V_{\mathrm{2}}\right|=\mathrm{1}$且$\left|E_{\mathrm{12}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{0}$。

情形（7） $\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$。

情形（8） 存在$v\in V_{\mathrm{0}}$满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$。

情形（9） 排除以上8种情形，可知$\left|V_{\mathrm{2}}\right|=\mathrm{0}$，$\left|E_{\mathrm{11}}\right|=\mathrm{0}$且对于$v\in V_{\mathrm{0}}$均满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|\le \mathrm{2}$。根据意大利控制的定义，当$i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$时，一定存在顶点$v_i$满足$f(v_i)=\mathrm{1}$。

下面将证明情形（6）~（9）也满足：当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f\left(v\right)>\mathrm{0.2}$；当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f\left(v\right)>\mathrm{0.4}$。

情形（6） $\left|V_{\mathrm{2}}\right|=\mathrm{1}$且$\left|E_{\mathrm{12}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{0}$。可令$f\left(v_{\mathrm{0}}\right)=\mathrm{2}$或$f\left(v_{\mathrm{1}}\right)=\mathrm{2}$。当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，由命题4，$r_f(v)\ge \mathrm{0.4}>\mathrm{0.2}$。

当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，用反证法，假设$r_f(v)\le \mathrm{0.4}$。

若$f(v_{\mathrm{0}})=\mathrm{2}$，则由$\left|V_{\mathrm{2}}\right|=\mathrm{1}$，$\left|E_{\mathrm{12}}\right|=\mathrm{0}$可得$f(v_{\mathrm{1}})=f(v_{\mathrm{2}})=\mathrm{0}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{1}$并排除情形（5）可得$f(v_{\mathrm{3}})=f(v_{\mathrm{4}})=\mathrm{0}$。由意大利控制的定义知，$f(v_{\mathrm{5}})=\mathrm{1}$。于是，$v_{\mathrm{1}}\in V_{\mathrm{0}}$且$\left|N(v_{\mathrm{1}})\bigcap V_{\mathrm{1}}\right|=\left|N(v_{\mathrm{1}})\bigcap V_{\mathrm{2}}\right|=\mathrm{1}$。由命题6知，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，与假设矛盾。

若$f(v_{\mathrm{1}})=\mathrm{2}$，由$\left|V_{\mathrm{2}}\right|=\mathrm{1}$，$\left|E_{\mathrm{12}}\right|=\mathrm{0}$可得$f(v_{\mathrm{0}})=f(v_{\mathrm{5}})=\mathrm{0}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{1}$并排除情形（5）可得$f(v_{\mathrm{2}})=\mathrm{0}$。由意大利控制的定义可得，$f(v_{\mathrm{3}})=f(v_{\mathrm{4}})=\mathrm{1}$。于是，$v_{\mathrm{5}}\in V_{\mathrm{0}}$且$\left|N(v_{\mathrm{5}})\bigcap V_{\mathrm{1}}\right|=\left|N(v_{\mathrm{5}})\bigcap V_{\mathrm{2}}\right|=\mathrm{1}$。由命题6，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。

图3给出了情形（6）中意大利控制函数的示意图，图中黑色实心点表示$f\left(v\right)=\mathrm{0}$的顶点，空心圆圈表示$f\left(v\right)=\mathrm{1}$的顶点，较大的空心圆圈表示$f\left(v\right)=\mathrm{2}$的顶点。

图3 情形(6)中的意大利控制函数f的示意图

Fig. 3 Italian domination function f in Case (6)

情形（7） $\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$。当$n\equiv$$\mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，根据命题5，$r_f(v)\ge \mathrm{0.4}>\mathrm{0.2}$。

当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，用反证法，假设$r_f(v)\le \mathrm{0.4}$。

令$f(v_{\mathrm{0}})=f(v_{\mathrm{1}})=\mathrm{1}$或$f(v_{\mathrm{0}})=f(v_{\mathrm{2}})=\mathrm{1}$或$f(v_{\mathrm{1}})=f(v_{\mathrm{5}})=\mathrm{1}$。

如果$f(v_{\mathrm{0}})=f(v_{\mathrm{1}})=\mathrm{1}$，由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$，则$f(v_{\mathrm{2}})=f(v_{\mathrm{5}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{4}})=\mathrm{1}$。 $f(v_{\mathrm{3}})$可以是1也可以是0。若$f(v_{\mathrm{3}})=\mathrm{1}$，则$\left|N(v_{\mathrm{2}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{3}})=\mathrm{0}$，由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$，则$f(v_{\mathrm{6}})=\mathrm{0}$。然后由意大利控制的定义，$f(v_{\mathrm{7}})=\mathrm{1}$。$f(v_{\mathrm{8}})=\mathrm{1}$或0。若$f(v_{\mathrm{8}})=\mathrm{1}$，则$\left|N(v_{\mathrm{6}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{8}})=\mathrm{0}$，根据意大利控制的定义，$f(v_{\mathrm{9}})=\mathrm{1}$。于是，$f(v_{\mathrm{5}})=\mathrm{0}$且$\left|N(v_{\mathrm{5}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。

如果$f(v_{\mathrm{0}})=f(v_{\mathrm{2}})=\mathrm{1}$，由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$，则$f(v_{\mathrm{1}})=f(v_{\mathrm{3}})=f(v_{\mathrm{4}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{5}})=\mathrm{1}$。$f(v_{\mathrm{6}})=\mathrm{1}$或0。若$f(v_{\mathrm{6}})=\mathrm{1}$，则$\left|N(v_{\mathrm{4}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{6}})=\mathrm{0}$，根据意大利控制的定义，$f(v_{\mathrm{7}})=f(v_{\mathrm{8}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{9}})=f(v_{\mathrm{10}})=f(v_{\mathrm{11}})=\mathrm{0}$。然后由意大利控制的定义可得，$f(v_{\mathrm{12}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{13}})=f(v_{\mathrm{14}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{15}})=\mathrm{1}$。$f(v_{\mathrm{16}})=\mathrm{1}$或0。若$f(v_{\mathrm{16}})=\mathrm{1}$，则$\left|N(v_{\mathrm{14}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{16}})=\mathrm{0}$，根据意大利控制的定义，$f(v_{\mathrm{17}})=f(v_{\mathrm{18}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{19}})=f(v_{\mathrm{20}})=f(v_{\mathrm{21}})=\mathrm{0}$。这样下去，可得：当$i\equiv \mathrm{2,5},\mathrm{7,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{1}$；当$i\equiv$$\mathrm{3,4},\mathrm{6,9},\mathrm{10,11}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{0}$。因为$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{2}$，则$\mathrm{2}n-\mathrm{2}=\mathrm{10}q+\mathrm{2}$，故$v_{\mathrm{2}n-\mathrm{2}}\in V_{\mathrm{1}},v_{\mathrm{0}}\in V_{\mathrm{1}}$且$(v_{\mathrm{2}n-\mathrm{2}},v_{\mathrm{0}})\in E$，由命题5，$r_f(v)\ge \mathrm{0.8}>\mathrm{0.4}$，矛盾。

如果$f(v_{\mathrm{1}})=f(v_{\mathrm{5}})=\mathrm{1}$，由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{0}})=f(v_{\mathrm{4}})=f(v_{\mathrm{9}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{2}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{3}})=\mathrm{0}$。$f(v_{\mathrm{6}})=\mathrm{0}$或1。若$f(v_{\mathrm{6}})=\mathrm{1}$，则$v_{\mathrm{4}}\in V_{\mathrm{0}}$且$\left|N(v_{\mathrm{4}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{6}})=\mathrm{0}$，根据意大利控制函数的定义，$f(v_{\mathrm{7}})=f(v_{\mathrm{8}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{10}})=f(v_{\mathrm{11}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{12}})=\mathrm{1}$。再由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，则$f(v_{\mathrm{13}})=f(v_{\mathrm{14}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{15}})=\mathrm{1}$。$f(v_{\mathrm{16}})=\mathrm{0}$或1。若$f(v_{\mathrm{16}})=\mathrm{1}$，则$\left|N(v_{\mathrm{14}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。若$f(v_{\mathrm{16}})=\mathrm{0}$，根据意大利控制的定义，$f(v_{\mathrm{17}})=f(v_{\mathrm{18}})=\mathrm{1}$。由$\left|E_{\mathrm{11}}\right|=\mathrm{1}$且$\left|V_{\mathrm{2}}\right|=\mathrm{0}$知，$f(v_{\mathrm{19}})=f(v_{\mathrm{20}})=f(v_{\mathrm{21}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{22}})=\mathrm{1}$。这样下去，可得：当$i\equiv \mathrm{2,5},\mathrm{7,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{1}$；当$i\equiv \mathrm{3,4},\mathrm{6,9},\mathrm{10,11}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{0}$。因为$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{2}$，则$\mathrm{2}n-\mathrm{2}=\mathrm{10}q+\mathrm{2}$，故$v_{\mathrm{2}n-\mathrm{2}}\in V_{\mathrm{1}},v_{\mathrm{0}}\in V_{\mathrm{0}}$且$\left|N(v_{\mathrm{0}})\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$，由命题3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}$，矛盾。

图4给出了情形（7）中意大利控制函数示意图，图中黑色实心点表示$f(v)=\mathrm{0}$的顶点，空心圆圈表示$f(v)=\mathrm{1}$的顶点。

图4 情形(7)中的意大利控制函数f的示意图

Fig. 4 Italian domination function f in Case (7)

情形（8） 存在$v\in V_{\mathrm{0}}$，满足$\left|N(v)\bigcap V_{\mathrm{1}}\right|=\mathrm{3}$。用反证法，假设当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)\le \mathrm{0.2}$；当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)\le \mathrm{0.4}$。

令$f(v_{\mathrm{2}})=\mathrm{0}$，$f(v_{\mathrm{0}})=f(v_{\mathrm{3}})=f(v_{\mathrm{4}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$知，则$f(v_{\mathrm{1}})=f(v_{\mathrm{5}})=f(v_{\mathrm{6}})=f(v_{\mathrm{7}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{8}})=f(v_{\mathrm{9}})=\mathrm{1}$。于是，$(v_{\mathrm{8}},v_{\mathrm{9}})\in E$，由命3和命题5，$r_f(v)\ge \mathrm{0.6}>\mathrm{0.4}>\mathrm{0.2}$，矛盾。

图5给出了情形（8）中意大利控制函数的示意图。

图5 情形(8)中的意大利控制函数f的示意图

Fig. 5 Italian domination function f in Case (8)

情形（9） 存在$v_i$满足$f\left(v_{\mathrm{i}}\right)=\mathrm{1}$且$i\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2})$。用反证法，假设当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)\le \mathrm{0.2}$；当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)\le \mathrm{0.4}$。

令$f(v_{\mathrm{0}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$知，则$f(v_{\mathrm{1}})=f(v_{\mathrm{2}})=\mathrm{0}$。$f(v_{\mathrm{3}})=\mathrm{1}$或0。

若$f(v_{\mathrm{3}})=\mathrm{1}$，排除情形（8），$f(v_{\mathrm{4}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{5}})=f(v_{\mathrm{6}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$知，$f(v_{\mathrm{7}})=f(v_{\mathrm{8}})=f(v_{\mathrm{9}})=\mathrm{0}$。然后由意大利控制的定义，$f(v_{\mathrm{10}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$，$f(v_{\mathrm{11}})=f(v_{\mathrm{12}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{13}})=\mathrm{1}$。排除情形（8），$f(v_{\mathrm{14}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{15}})=f(v_{\mathrm{16}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$，$f(v_{\mathrm{17}})=$$f(v_{\mathrm{18}})=$$f(v_{\mathrm{19}})=\mathrm{0}$。排除情形（8），$f(v_{\mathrm{21}})=\mathrm{0}$。根据意大利控制的定义，$f(v_{\mathrm{20}})=\mathrm{1}$。这样下去，可得：当$i\equiv \mathrm{3},$$\mathrm{5,6},$$\mathrm{10}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{1}$；当$i\equiv \mathrm{2,4},\mathrm{7,8},\mathrm{9,11}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{0}$。若$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{1}$，$\mathrm{2}n-\mathrm{2}=\mathrm{10}q$，故$f(v_{\mathrm{2}n-\mathrm{2}})=\mathrm{1}$，则$v_{\mathrm{2}n-\mathrm{2}},v_{\mathrm{0}}\in V_{\mathrm{1}}$且$(v_{\mathrm{2}n-\mathrm{2}},v_{\mathrm{0}})\in E$。若$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{2}$，则$\mathrm{2}n-\mathrm{1}=\mathrm{10}q+\mathrm{3}$，故$f(v_{\mathrm{2}n-\mathrm{1}})=\mathrm{1}$，则$v_{\mathrm{3}},v_{\mathrm{2}n-\mathrm{1}}\in V_{\mathrm{1}}$且$(v_{\mathrm{3}},v_{\mathrm{2}n-\mathrm{1}})\in E$。根据情形（7），当$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)>\mathrm{0.2}$；当$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，$r_f(v)>\mathrm{0.4}$，矛盾。

若$f(v_{\mathrm{3}})=\mathrm{0}$，根据意大利控制的定义，$f(v_{\mathrm{4}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$，则$f(v_{\mathrm{5}})=f(v_{\mathrm{6}})=\mathrm{0}$。由意大利控制的定义，$f(v_{\mathrm{7}})=\mathrm{1}$。排除情形（8），$f(v_{\mathrm{8}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{9}})=f(v_{\mathrm{10}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$，则$f(v_{\mathrm{11}})=f(v_{\mathrm{12}})=f(v_{\mathrm{13}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{14}})=\mathrm{1}$。再排除情形（8），$f(v_{\mathrm{15}})=f(v_{\mathrm{16}})=\mathrm{0}$。然后可得，$f(v_{\mathrm{17}})=\mathrm{1}$。排除情形（8），$f(v_{\mathrm{18}})=\mathrm{0}$，然后可得，$f(v_{\mathrm{19}})=f(v_{\mathrm{20}})=\mathrm{1}$。由$\left|V_{\mathrm{2}}\right|=\mathrm{0}$且$\left|E_{\mathrm{11}}\right|=\mathrm{1}$，$f(v_{\mathrm{21}})=\mathrm{0}$。这样下去，可得：当$i\equiv \mathrm{4,7},\mathrm{9,10}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{1}$；当$i\equiv \mathrm{2,3},\mathrm{5,6},\mathrm{8,11}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，$f(v_i)=\mathrm{0}$。若$n\equiv \mathrm{1}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{1}$，则$\mathrm{2}n-\mathrm{2}=\mathrm{10}q$，故$f(v_{\mathrm{2}n-\mathrm{2}})=\mathrm{1}$，于是$v_{\mathrm{2}n-\mathrm{2}},v_{\mathrm{0}}\in V_{\mathrm{1}}$且$(v_{\mathrm{2}n-\mathrm{2}},v_{\mathrm{0}})\in E$。根据情形（7），$r_f(v)>\mathrm{0.2}$，矛盾。若$n\equiv \mathrm{2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$，可令$n=\mathrm{5}q+\mathrm{2}$，则$\mathrm{2}n-\mathrm{1}=\mathrm{10}q+\mathrm{3}$，故$f(v_{\mathrm{2}n-\mathrm{1}})=\mathrm{1}$，于是$\left|N(v_{\mathrm{3}})\bigcap V_{\mathrm{0}}\right|=\mathrm{2}$，这种情况不满足意大利控制函数的定义。因此，$r_f(v)\le \mathrm{0.4}$不成立。

图6给出了情形（9）中的意大利控制函数示意图。

图6 情形(9)中的意大利控制函数f的示意图

Fig. 6 Italian domination function f in Case (9)

由定理10和定理13，可得定理14。

定理14  当$n\equiv \mathrm{0,3},\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$；当$n\equiv \mathrm{1,2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。

2.3　P（n，2）意大利控制数与2-彩虹控制数和经典控制数的关系

根据定理9和定理14，可以得到定理15。

定理15  当$n\equiv \mathrm{0,1},\mathrm{2,3},\mathrm{4,6},\mathrm{7,9}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))={\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))$；当$n\equiv \mathrm{5,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))={\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))-\mathrm{1}$。

定理16  ^［12］     若$n\ge \mathrm{5}$，则$\gamma \left(P(n,\mathrm{2})\right)=⌈\frac{\mathrm{3}n}{\mathrm{5}}⌉$。

根据定理14和定理16，可以得到定理17。

定理17   ${\gamma }_I(P(n,\mathrm{2}))\ne \mathrm{2}\gamma (P(n,\mathrm{2}))$，因此P（n，2）不是意大利图。

3 结论

本文主要研究了广义Petersen图P（n，1）和P（n，2）的意大利控制数。通过构造可递推的意大利控制函数得到P（n，1）和P（n，2）意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n，1）和P（n，2）意大利数的下界。最终确定了P（n，1）和P（n，2）意大利控制数的精确值：${\gamma }_I(P(n,\mathrm{1}))=n$；当$n\equiv \mathrm{0,3},\mathrm{4}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉$；当$n\equiv \mathrm{1,2}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{5})$时，${\gamma }_I(P(n,\mathrm{2}))=⌈\frac{\mathrm{4}n}{\mathrm{5}}⌉+\mathrm{1}$。同时还得到了P（n，1）和P（n，2）意大利控制数与2‒彩虹控制数之间的关系：${\gamma }_I(P(n,\mathrm{1}))={\gamma }_{r\mathrm{2}}(P(n,\mathrm{1}))$；当$n\equiv \mathrm{5,8}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{10})$时，${\gamma }_I(P(n,\mathrm{2}))=$${\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))-\mathrm{1}$；否则，${\gamma }_I(P(n,\mathrm{2}))={\gamma }_{r\mathrm{2}}(P(n,\mathrm{2}))$。

此外，当$n\equiv \mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，P（n，1）是意大利图；当$n\cancel{\equiv }\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{4})$时，P（n，1）不是意大利图。P（n，2）不是意大利图。

作者贡献声明

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

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

尹亚男：论文初稿的写作，程序调试。

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