高 紅，黃佳歡，栗 坤，楊元生

（1.大連海事大學(xué)理學(xué)院，遼寧 大連 116026；2.大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024）

在圖G=(V，E)中，V表示頂點(diǎn)的集合，E表示邊的集合。頂點(diǎn)v∈V的開(kāi)鄰域是與v有邊相連的頂點(diǎn)構(gòu)成的集合，即N(v)={u|u是頂點(diǎn)且(uv)∈E}。N(v)中包含的頂點(diǎn)的個(gè)數(shù)稱為頂點(diǎn)v的度，記為deg(v)。圖G的最小度和最大度分別記為δ和Δ。圖G頂點(diǎn)的個(gè)數(shù)稱為圖G的階。Pn表示階為n的路徑圖。

圖的羅馬控制起源于古羅馬帝國(guó)的軍事防御問(wèn)題［1］。古羅馬帝國(guó)的每個(gè)城市最多能安置2支軍隊(duì)駐守。對(duì)于沒(méi)有軍隊(duì)駐守的城市，其相鄰的城市中必須至少有一個(gè)城市安置2支軍隊(duì)駐守，以便在該城市受到侵犯時(shí)相鄰的城市能派出1支軍隊(duì)來(lái)支援。在這種歷史背景下產(chǎn)生了圖的羅馬控制，定義為：在圖G=(V，E)中，f為從頂點(diǎn)集合V到數(shù)集{0，1，2}的函數(shù)，如果每一個(gè)函數(shù)值為0的頂點(diǎn)v都至少與一個(gè)函數(shù)值為2的頂點(diǎn)相鄰，則f為圖G的羅馬控制函數(shù)。f的權(quán)重圖G的所有羅馬控制函數(shù)權(quán)重的最小值稱為圖G的羅馬控制數(shù)，記為γR(G)。關(guān)于羅馬控制的相關(guān)研究結(jié)果可以參考文獻(xiàn)［2-5］。

意大利控制［6］是羅馬控制的一種變形，也稱為羅馬｛2｝-控制［7］或弱｛2｝-控制［8］，定義為：設(shè)圖G=(V，E)，函數(shù)f∶V→{0，1，2}，如果每一個(gè)函數(shù)值為0的頂點(diǎn)v都至少與一個(gè)函數(shù)值為2的頂點(diǎn)相鄰或者至少與2個(gè)函數(shù)值為1的頂點(diǎn)相鄰，那么f稱為圖G的意大利控制函數(shù)。f的權(quán)重權(quán)重的最小值稱為圖G的意大利控制數(shù)，記為γI(G)。若f滿足w(f)=γI(G)，則稱f為圖G的γI-函數(shù)。

意大利控制是圖的控制理論中較為活躍的研究課題，吸引了很多學(xué)者。文獻(xiàn)［6］中研究了意大利控制數(shù)與羅馬控制數(shù)、彩虹控制數(shù)、經(jīng)典控制數(shù)的關(guān)系，并證明了任意圖的意大利控制數(shù)都小于等于其2-彩虹控制數(shù)。文獻(xiàn)［7］中研究了樹(shù)圖T的意大利控制數(shù)，確定了分別滿足γ(T)+1=γI(T)和2γ(T)=γI(T)的樹(shù)圖的特點(diǎn)，其中γ(T)是樹(shù)圖的控制數(shù)。文獻(xiàn)［8］中給出了圈Cn與C5的笛卡爾乘積Cn□C5的意大利控制數(shù)下界，并確定了Cn□C3和Cn□C4意大利控制數(shù)的精確值。文獻(xiàn)［9］中確定了廣義彼得森圖P(n，3)意大利控制數(shù)的精確值。文獻(xiàn)［10］中研究了有向圈乘積圖的意大利控制數(shù)。文獻(xiàn)［11］中研究了有根乘積圖的意大利控制數(shù)。學(xué)者們還研究了與意大利控制相關(guān)的全局意大利控制［12］、獨(dú)立意大利控制［13］、完美意大利控制［14-16］、符號(hào)意大利控制［17］、全意大利控制［18］、外獨(dú)立意大利控制［19］、限制意大利控制［20］、安全意大利控制［21］等。

直積圖，也稱為克羅內(nèi)克乘積圖，是一種重要的圖類，在實(shí)際中應(yīng)用廣泛，如在計(jì)算機(jī)通信網(wǎng)絡(luò)、多處理器管理等領(lǐng)域。文獻(xiàn)［22-23］中分別研究了直積圖上的經(jīng)典控制和完美控制。對(duì)于給定的2個(gè)圖G和H，它們的直積圖G×H=(V，E)，其中頂點(diǎn)的集合為V(G×H)={(u，v)|u∈V(G)，v∈V(H)}，邊 的 集 合 為E(G×H)={(u1，v1)(u2，v2)|u1u2∈E(G)，v1v2∈E(H)}。

本研究中確定了Pn×P1、Pn×P2和Pn×P3意大利控制數(shù)的精確值，并給出了Pn×Pm(m≥4)意大利控制數(shù)的界。

以下是與本研究相關(guān)的定理：

定 理1［7］若 圖G為 路 徑 圖Pn，則γI(G)=

定 理2［7］若 圖G為 連 通 圖，則γI(G)≥

1 Pn×P1和Pn×P2意大利控制數(shù)

Pn×P1是n個(gè)孤立點(diǎn)，因此可知Pn×P1的意大利控制數(shù)為n，即：

定理3對(duì)于任意的正整數(shù)n≥1，γI(Pn×P1)=n。

由于Pn×P2與2條不相交的路徑圖Pn是同構(gòu)的，因此γI(Pn×P2)=2γI(Pn)。由定理1，可得以下定理：

定理4令G=Pn×P2，則

2 Pn×P3意大利控制數(shù)

2.1 Pn×Pm意大利控制數(shù)的上界

通過(guò)構(gòu)造路徑直積圖的意大利控制函數(shù)可以得到γI(Pn×Pm)(m≥3)的上界。

定理5對(duì)于任意的正整數(shù)m≥3，n≥m，k≥2，有：

證明：設(shè)G=Pn×Pm的頂點(diǎn)集合為V={vi，j|0≤i≤n-1，0≤j≤m-1}，其中i是頂點(diǎn)的行標(biāo)號(hào)，j是頂點(diǎn)的列標(biāo)號(hào)。

（1）當(dāng)m=3k時(shí)，按照下式構(gòu)造意大利控制函數(shù)f：

圖1顯示了P7×P6上的意大利控制函數(shù)f，其中Rn(Rm)表示隨著n(m)的增長(zhǎng)，重復(fù)相應(yīng)的1行（3列）。圖1中，空心圓圈表示f(vi，j)=0的頂點(diǎn)，黑色實(shí)心點(diǎn)表示f(vi，j)=1的頂點(diǎn)，較大的粗邊空心圓圈表示f(vi，j)=2的頂點(diǎn)。

圖1 P7×P6上的意大利控制函數(shù)fFig.1 Italian dominating function f on P7×P6

（2）當(dāng)m=3k-1時(shí)，分2種情況構(gòu)造意大利控制函數(shù)f。

當(dāng)n為偶數(shù)時(shí)，

當(dāng)n為奇數(shù)時(shí)，

圖2顯示了P6×P5和P7×P5上的意大利控制函數(shù)f，其中Rn(Rm)表示隨著n(m)的增長(zhǎng)，重復(fù)相應(yīng)的2行（3列）。

圖2 P6×P5和P7×P5上的意大利控制函數(shù)fFig.2 Italian dominating function f on P6×P5 and P7×P5

（3）當(dāng)m=3k-2時(shí)，分3種情況構(gòu)造意大利控制函數(shù)f。

當(dāng)n≡0(mod 3)時(shí)，

當(dāng)n≡1(mod 3)時(shí)，

當(dāng)n≡2(mod 3)時(shí)，

圖3顯示了P9×P7、P10×P7和P14×P7上的意大利控制函數(shù)f，其中Rn(Rm)表示隨著n(m)的增長(zhǎng)，重復(fù)相應(yīng)的3行（3列）。

可以驗(yàn)證，按照以上方式構(gòu)造的f均為意大利控制函數(shù)。根據(jù)f的定義并結(jié)合圖示，可以計(jì)算得到f的權(quán)重，如下所示：

因此，可得

即：

根據(jù)定理5，可以得到Pn×P3意大利控制數(shù)的上界，即有以下的推論：

推論1對(duì)于任意的正整數(shù)n≥3，γI(Pn×P3)≤n+2。

2.2 Pn×P3意大利控制數(shù)的下界

本節(jié)中證明Pn×P3意大利控制數(shù)的下界也是n+2。令G=Pn×P3，頂 點(diǎn) 集V(G)={vi，j|0≤i≤n-1，0≤j≤2}，f是G上的意大利控制函數(shù)，記Vi={vi，j|0≤j≤2}(0≤i≤n-1)，fi=f(Vi)=

引理1在圖Pn×P3中，若f為Pn×P3的意大利控制函數(shù)，則以下結(jié)論均成立：

（1）若fi=0(1≤i≤n-2)，則fi-1+fi+1≥4。

（2）若f0=0，則f1≥4；若f0=1，則f1≥2；若f0=2，則f1≥2。若fn-1=0，則fn-2≥4；若fn-1=1，則fn-2≥2；若fn-1=2，則fn-2≥2。

（3）f0+f1≥3；若f0=1，f1≤3，則f2≥1。fn-1+fn-2≥3；若fn-1=1，fn-2≤3，則fn-3≥1。

（4）f0+f1+f2≥4，fn-1+fn-2+fn-3≥4。

（5）fi-1+fi+fi+1≥3(2≤i≤n-3)。

證明：（1）若fi=0(1≤i≤n-1)，有f(vi，0)=f(vi，1)=f(vi，2)=0，則

由fi-1+fi+1≥4可 知，若fi-1=0，1，2，3，則fi+1≥4，3，2，1；若fi-1≥4，則fi+1≥0。因此，fi-1和fi+1要么滿足fi-1=2且fi+1≥2，要么滿足fi-1≥3或fi+1≥3。

（2）若f0=0，則

若f0=1，則f(v0，0)和f(v0，2)中至少有一個(gè)等于0，所以f(v1，1)=2，即f1≥2。若f0=2，則f(v0，0)、f(v0，1)和f(v0，2)中 至 少 有 一 個(gè) 等 于0，所 以 有f(v1，1)=2或者f(v1，0)+f(v1，2)≥2，即有f1≥2。

同理可得，若fn-1=0，則fn-2≥4；若fn-1=1，則fn-2≥2；若fn-1=2，則fn-2≥2。

（3）當(dāng)f0≥3時(shí)，顯 然 有f0+f1≥3。當(dāng)f0＜3時(shí)，由本引理第2條結(jié)論，即由（2）可知，f0+f1≥3，并且由（2）的證明可知，若f0=1，則f(v1，1)=2。若f1≤3，則f(v1，0)和f(v1，2)中至少有一個(gè)等于0。由于f0=1，根據(jù)意大利控制函數(shù)的定義，f2≥1。

同理可得，fn-1+fn-2≥3；若fn-1=1，fn-2≤3，則fn-3≥1。

（4）根據(jù)本引理的（2）和（3），有f0+f1+f2≥4，fn-1+fn-2+fn-3≥4。

（5）若fi=0，由本引理（1）可知，fi-1+fi+1≥4，所以fi-1+fi+fi+1≥3。若fi=1或2，則f(vi，0)、f(vi，1)和f(vi，2)中至少有一個(gè)為0，故f(vi-1，1)+f(vi+1，1)≥2或f(vi-1，0)+f(vi-1，2)+f(vi+1，0)+f(vi+1，2)≥2，故fi-1+fi+fi+1≥3。

定理6γI(P3×P3)=4。

證明：在圖P3×P3中構(gòu)造意大利控制函數(shù)f：f(v1，0)=f(v1，2)=1，f(v1，1)=2，其他頂點(diǎn)f(vi，j)=0。f為意大利控制函數(shù)且f的權(quán)重w(f)=4，所以γI(P3×P3)≤4。根據(jù)引理1（4）可知f0+f1+f2≥4，所以γI(P3×P3)=4。

定理7對(duì)于任意的正整數(shù)n≥4，γI(Pn×P3)≥n+2。

證明：在圖G=Pn×P3中，頂點(diǎn)集合V(G)={vi，j|0≤i≤n-1，0≤j≤2}，Vi={vi，j|0≤j≤2}(0≤i≤n-1)，f為Pn×P3的γI-函數(shù)，fi=f(Vi)=

由引理1（3）、（4）、（5）可知，f0+f1≥3，fn-1+fn-2≥3，f0+f1+f2≥4，fn-1+fn-2+fn-3≥4，fi-1+fi+fi+1≥3(2≤i≤n-3)。

當(dāng)n≡0(mod 3)時(shí)，

當(dāng)n≡1(mod 3)時(shí)，

當(dāng)n≡2(mod 3)時(shí)，

綜上，γI(Pn×P3)≥n+2。

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

定理8對(duì)于任意的正整數(shù)n≥4，γI(Pn×P3)=n+2。

3 Pn×Pm（m≥4）意大利控制數(shù)的界

由于Δ(Pn×Pm)=4且|V(G)|=mn，因此根據(jù)定理2可以得到推論2。

推論2若G=Pn×Pm，則

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

定理9對(duì)于任意的正整數(shù)m≥4且n≥m，有：

4 結(jié)語(yǔ)

研究了路徑直積圖Pn×Pm的意大利控制數(shù)，確定了一些路徑直積圖的意大利控制數(shù)，γI(Pn×P1)=n；當(dāng)n≡1(mod 2)時(shí)，γI(Pn×P2)=n+1；當(dāng)n≡0(mod 2)時(shí)，γI(Pn×P2)=n+2；γI(P3×P3)=4；γI(Pn×P3)=n+2(n≥4)。對(duì)于m，n≥4，利用可遞推的方法構(gòu)造了Pn×Pm的意大利控制函數(shù)，從而給出了γI(Pn×Pm)的界。這種可遞推的方法可以用于有任意多頂點(diǎn)的圖類，實(shí)現(xiàn)用有限的方法解決無(wú)限的問(wèn)題。

作者貢獻(xiàn)聲明：

高紅：證明方法提出，算法總體設(shè)計(jì)，論文定稿。

黃佳歡：論文寫(xiě)作，畫(huà)圖，程序編寫(xiě)。

栗坤：論文初稿的寫(xiě)作，程序調(diào)試。

楊元生：方法指導(dǎo)，程序設(shè)計(jì)指導(dǎo)。