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

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

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

在圖G=（V，E）中，若D ?V(G)且N [D]=V(G)，則稱D為G的一個(gè)控制集?？刂萍貍€(gè)數(shù)的最小值稱為圖G的控制數(shù)，記為γ(G)。圖的控制有很多種類型，其中意大利控制［1］是一種新興的控制類型，又稱為羅馬｛2｝?控制［2］或弱｛2｝?控制［3］。設(shè)f：V →{0，1，2}為圖G上的函數(shù)，如果所有滿足f(v)=0 的頂點(diǎn)v 在其鄰域中至少有一個(gè)被賦值為2的頂點(diǎn)或者至少有兩個(gè)被賦值為1的頂點(diǎn)，那么函數(shù)f 稱為圖G 的意大利控制函數(shù)。意大利控制函數(shù)的權(quán)重等于圖G 中所有頂點(diǎn)的函數(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)于意大利控制的研究可以參考文獻(xiàn)［4-10］。

本文研究了廣義Petersen 圖P（n，1）和P（n，2）意大利控制數(shù)。通過(guò)構(gòu)造可遞推的意大利控制函數(shù)計(jì)算出意大利控制數(shù)的上界。利用袋裝法和控制代價(jià)函數(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 個(gè)頂點(diǎn)。圖1a和1b顯示的是P（6，1）和P（6，2）。為了便于表示Petersen 圖的意大利控制函數(shù)，本文將P（n，k）表示為剪開(kāi)的形式，圖1c和1d顯示的是P（6，1）和P（6，2）的剪開(kāi)圖。

設(shè)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ù)的示意圖，圖中黑色實(shí)心點(diǎn)表示f (v)=0的頂點(diǎn)，空心圓圈表示f (v)=1的頂點(diǎn)，較大的空心圓圈表示f (v)=2的頂點(diǎn)。

圖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é)論

作者貢獻(xiàn)說(shuō)明：

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

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

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

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