路徑直積圖的意大利控制數(shù)

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

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

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

圖的羅馬控制起源于古羅馬帝國的軍事防御問題［1］。古羅馬帝國的每個城市最多能安置2支軍隊駐守。對于沒有軍隊駐守的城市，其相鄰的城市中必須至少有一個城市安置2支軍隊駐守，以便在該城市受到侵犯時相鄰的城市能派出1支軍隊來支援。在這種歷史背景下產(chǎn)生了圖的羅馬控制，定義為：在圖G=(V，E)中，f為從頂點集合V到數(shù)集{0，1，2}的函數(shù)，如果每一個函數(shù)值為0的頂點v都至少與一個函數(shù)值為2的頂點相鄰，則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}，如果每一個函數(shù)值為0的頂點v都至少與一個函數(shù)值為2的頂點相鄰或者至少與2個函數(shù)值為1的頂點相鄰，那么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］中研究了樹圖T的意大利控制數(shù)，確定了分別滿足γ(T)+1=γI(T)和2γ(T)=γI(T)的樹圖的特點，其中γ(T)是樹圖的控制數(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］、獨立意大利控制［13］、完美意大利控制［14-16］、符號意大利控制［17］、全意大利控制［18］、外獨立意大利控制［19］、限制意大利控制［20］、安全意大利控制［21］等。

直積圖，也稱為克羅內(nèi)克乘積圖，是一種重要的圖類，在實際中應(yīng)用廣泛，如在計算機(jī)通信網(wǎng)絡(luò)、多處理器管理等領(lǐng)域。文獻(xiàn)［22-23］中分別研究了直積圖上的經(jīng)典控制和完美控制。對于給定的2個圖G和H，它們的直積圖G×H=(V，E)，其中頂點的集合為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個孤立點，因此可知Pn×P1的意大利控制數(shù)為n，即：

定理3對于任意的正整數(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ù)的上界

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

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

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

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

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

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

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

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

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

圖2顯示了P6×P5和P7×P5上的意大利控制函數(shù)f，其中Rn(Rm)表示隨著n(m)的增長，重復(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時，分3種情況構(gòu)造意大利控制函數(shù)f。

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

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

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

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

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

因此，可得

即：

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

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

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

本節(jié)中證明Pn×P3意大利控制數(shù)的下界也是n+2。令G=Pn×P3，頂 點 集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)中至少有一個等于0，所以f(v1，1)=2，即f1≥2。若f0=2，則f(v0，0)、f(v0，1)和f(v0，2)中 至 少 有 一 個 等 于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時，顯 然 有f0+f1≥3。當(dāng)f0＜3時，由本引理第2條結(jié)論，即由（2）可知，f0+f1≥3，并且由（2）的證明可知，若f0=1，則f(v1，1)=2。若f1≤3，則f(v1，0)和f(v1，2)中至少有一個等于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)中至少有一個為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，其他頂點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對于任意的正整數(shù)n≥4，γI(Pn×P3)≥n+2。

證明：在圖G=Pn×P3中，頂點集合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)時，

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

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

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

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

定理8對于任意的正整數(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對于任意的正整數(shù)m≥4且n≥m，有：

4 結(jié)語

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

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

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

黃佳歡：論文寫作，畫圖，程序編寫。

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

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