廣義Petersen圖P(n,1)和P(n,2)的意大利控制數(shù)

高 紅，黃佳歡，尹亞男，楊元生

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

G=（V，E）表示一個圖，頂點集合為V，邊的集合 為 E。 頂 點 v 的 開 鄰 域 為 N(v)={u|(u，v)∈E(G) }，閉鄰域為N [v]=N(v)∪{v}。頂點v 的度是N（v）中包含的頂點的個數(shù)，即deg(v)=|N(v)|。圖G的最大度和最小度分別記作Δ(G)和δ(G)。若對于任意的v ∈V，都有deg(v)=r，則圖G稱為r?正則圖。

在圖G=（V，E）中，若D ?V(G)且N [D]=V(G)，則稱D為G的一個控制集。控制集包含元素個數(shù)的最小值稱為圖G的控制數(shù)，記為γ(G)。圖的控制有很多種類型，其中意大利控制［1］是一種新興的控制類型，又稱為羅馬｛2｝?控制［2］或弱｛2｝?控制［3］。設f：V →{0，1，2}為圖G上的函數(shù)，如果所有滿足f(v)=0 的頂點v 在其鄰域中至少有一個被賦值為2的頂點或者至少有兩個被賦值為1的頂點，那么函數(shù)f 稱為圖G 的意大利控制函數(shù)。意大利控制函數(shù)的權(quán)重等于圖G 中所有頂點的函數(shù)值之和，權(quán)重的最小值為圖G的意大利控制數(shù)，記為γI(G)。若f 為圖G 的意大利控制函數(shù)并且w( f )=γI(G)，則f 稱為γI?function。若圖G 滿足2γ(G)=γI(G)，則稱圖G為意大利圖。關(guān)于意大利控制的研究可以參考文獻［4-10］。

本文研究了廣義Petersen 圖P（n，1）和P（n，2）意大利控制數(shù)。通過構(gòu)造可遞推的意大利控制函數(shù)計算出意大利控制數(shù)的上界。利用袋裝法和控制代價函數(shù)法分別證明出P（n，1）和P（n，2）意大利控制數(shù)的下界。最終確定了P（n，1）和P（n，2）意大利控制數(shù)的精確值。

1 P(n,1)的意大利控制數(shù)

1.1 P（n，1）意大利控制數(shù)的上界

廣義Petersen 圖P（n，k）是3 正則圖，有2n 個頂點。圖1a和1b顯示的是P（6，1）和P（6，2）。為了便于表示Petersen 圖的意大利控制函數(shù)，本文將P（n，k）表示為剪開的形式，圖1c和1d顯示的是P（6，1）和P（6，2）的剪開圖。

設G=P（n，k），f 為圖G 上的意大利控制函數(shù)，則有下面的形式：

1.2 P（n，1）意大利控制數(shù)的下界

圖1 Petersen 圖P（6，1）和P（6，2）Fig.1 Petersen graph P(6,1)and P(6,2)

2 P(n,2)的意大利控制數(shù)

2.1 P（n，2）意大利控制數(shù)的上界

2.2 P（n，2）意大利控制數(shù)的下界

圖2 命題2～8的示意圖Fig.2 Sketches for propositions 2 to 8

|N(v5)∩V2|=1。 由 命 題6，rf(v)≥0.6＞0.4，矛盾。

圖3 給出了情形（6）中意大利控制函數(shù)的示意圖，圖中黑色實心點表示f (v)=0的頂點，空心圓圈表示f (v)=1的頂點，較大的空心圓圈表示f (v)=2的頂點。

圖3 情形（6）中的意大利控制函數(shù)f的示意圖Fig.3 Italian domination function f in Case(6)

圖4 情形（7）中的意大利控制函數(shù)f的示意圖Fig.4 Italian domination function f in Case(7)

圖5 給出了情形（8）中意大利控制函數(shù)的示意圖。

情形（9）存在vi滿足f(vi)=1且i≡0(mod 2)。

圖5 情形（8）中的意大利控制函數(shù)f的示意圖Fig.5 Italian domination function f in Case(8)

2.3 P（n，2）意大利控制數(shù)與2-彩虹控制數(shù)和經(jīng)典控制數(shù)的關(guān)系

圖6 情形（9）中的意大利控制函數(shù)f的示意圖Fig.6 Italian domination function f in Case(9)

3 結(jié)論

作者貢獻說明：

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

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

尹亞男：論文初稿的寫作，程序調(diào)試。

楊元生：方法指導和程序設計指導。