徐加雪, 王志平

(大連海事大學理學院，大連 116000)

1 引言

對本文使用的符號和術(shù)語進行說明.圖G 是由頂點集合V(G)和邊集合E(G)構(gòu)成的一個簡單圖.n = |V(G)|表示圖G 的階數(shù)，|E(G)|表示圖G 的邊數(shù).對于圖中的每一個頂點v ∈V(G)，它的開鄰域和閉鄰域分別用N(v) = {u ∈V(G)|uv ∈E(G)}和N[v] =N(v)∪{v}對應表示.d(v) = |N(v)|表示頂點v 的度.f 代表定義在頂點集合V(G)上的函數(shù).f : V(G) →{0,1,2}即表示圖中任意的頂點v ∈V(G), f(v) = 0 或1 或2.?=?(G)和δ =δ(G)分別表示圖G 的最大度和最小度.

圖論起源于十八世紀，是一個有著豐富歷史背景和實用價值的學科.它是由日常生活中的游戲激發(fā)產(chǎn)生的，至今已經(jīng)有兩百多年的發(fā)展歷史.上個世紀中期，Clande Berge 學者根據(jù)國際象棋問題首先提出了圖的“控制數(shù)”的概念.受Berge 學者的啟示，Oystein Ore 學者正式提出了控制數(shù)以及相關(guān)方面的術(shù)語并延續(xù)至今.基于不同的實際應用背景以及歷史背景，圖的控制數(shù)衍生出許多新的控制參數(shù)，例如弱控制數(shù)、獨立控制數(shù)、距離控制數(shù)、符號邊控制、羅馬控制數(shù)等，控制數(shù)的種類不斷增加.

Stewart 在文獻[1]中講述了公元四世紀時羅馬帝國的君主保衛(wèi)國家的故事.我們把整個羅馬帝國視為一個圖，令圖中的點表示羅馬帝國中的每個地區(qū)，邊表示兩個地區(qū)相鄰.沒有軍隊駐扎的地區(qū)稱為不安全的地區(qū)，反之則稱其為安全的地區(qū).軍隊需要駐扎在不同的地區(qū)守護國家的領(lǐng)土安全.安全系數(shù)最高的方案是在羅馬帝國內(nèi)的每一個地區(qū)都駐扎一支軍隊.若國家長期處于和平時期，這種防御方案便會造成軍隊資源的浪費.君主希望在羅馬帝國內(nèi)的每個地區(qū)駐扎數(shù)量較少的軍隊，同時能夠維持國家的領(lǐng)土完整與安全，于是頒布了一條法令：從一個安全的地區(qū)派遣軍隊去往一個不安全的地區(qū)后，使安全的地區(qū)轉(zhuǎn)變?yōu)椴话踩貐^(qū)的情況不可以存在.根據(jù)君主的命令可知，只有至少駐扎兩個軍隊的安全地區(qū)才能夠往相鄰的不安全的地區(qū)派遣軍隊，這樣既能夠保證安全地區(qū)在派遣軍隊之后仍是安全的地區(qū)，相鄰的不安全的地區(qū)接收派遣的軍隊后也轉(zhuǎn)變?yōu)榘踩貐^(qū).在總結(jié)已有經(jīng)驗的基礎上，1999 年，Stewart 首次提出了羅馬控制概念[1].Cockayne 等學者[2]受保衛(wèi)羅馬帝國的歷史故事的啟發(fā)，正式給出了圖G 的頂點集合上的羅馬控制函數(shù)的定義，如下所示：

實際生活中，敵人更傾向于攻擊薄弱的地區(qū).當羅馬帝國的地區(qū)面臨敵人的多重攻擊時，駐扎兩個軍隊的安全地區(qū)，無法保護數(shù)量超過三個以上的不安全的鄰居，此時羅馬帝國很容易失守而落入敵人手中.于是Alvarezruiz 等學者[17]提出一種更符合實際情況的防御新策略，并且定義了圖G 的強羅馬控制函數(shù)，具體地，

是一個定義在圖G 的頂點集合V(G)上的函數(shù)，若每一個頂點v ∈B0至少存在一個鄰結(jié)點w ∈B2，且鄰結(jié)點w 滿足

其中

圖1 和圖2 分別給出了圖G 上的羅馬控制函數(shù)和強羅馬控制函數(shù).一次大地震過后往往會伴隨著許多余震的發(fā)生，數(shù)量有限的軍隊需要駐扎在災區(qū)，隨時準備營救受災群眾.假設村莊用圖中的點表示，村莊之間的路用圖中的邊表示.圖上的數(shù)字表示該村莊中駐扎軍隊的數(shù)量.當面臨多個村莊都需要營救時，圖1 中的軍隊不能夠及時營救它周圍所有受災的村莊，但圖2 中的軍隊至少能夠及時營救一半以上沒有軍隊駐扎的村莊，大大減少生命財產(chǎn)損失.

圖1: 圖G 的羅馬控制函數(shù)

圖2: 圖G 的強羅馬控制函數(shù)

人們往往希望利用一個多項式時間算法來求出所有圖上的控制數(shù)的精確值，但已有結(jié)論指出一般圖的控制問題是一個NP-完備問題，因此探究出圖的控制數(shù)或者控制數(shù)較好的上下界具有重大的理論意義.Alvarezruiz 等學者在文獻[17]中提出了一個開放性問題：所有階為n ≥3 的連通圖是否都有γStR(G)≤成立.為了驗證問題的正確性，本文應用數(shù)學歸納法和分類討論方法，深入地討論了圖的強羅馬控制數(shù)與階數(shù)的關(guān)系，得到了風車圖、完全二部圖、完全圖的刺圖等特殊圖上的強羅馬控制數(shù)均不大于其階數(shù)的七分之六，從而進一步說明了問題的正確性.

2 主要結(jié)論與證明

定理1若G 是一個階為n ≥3，最大度為?=n ?1 的圖，則γStR(G)≤.

證明 假設圖G 中的頂點v ∈V(G)的度為d(v) = ?= n ?1.在圖G 的頂點集V(G)上定義一個函數(shù)f :V(G)→{0,1,··· ,+1}，令f(v)=+1，而對任意的頂點x ∈N(v)，都有f(x) = 0.顯然，函數(shù)f 是圖G 的頂點集V(G)上一個強羅馬控制函數(shù)，因此

同理可知，風車圖、扇圖、鳳梨圖等都是階為n ≥3 且最大度為?=n ?1 的圖，所以這些特殊圖均滿足γStR(G)≤.

若圖G 的頂點集合V(G)劃分為兩個頂點子集V1、V2，且滿足在同一頂點子集的任意兩個頂點之間不存在邊且圖中的每條邊連接不同頂點子集中的頂點，則稱圖G 是一個二部圖. 若圖G 是一個二部圖，且頂點子集V1中的任意一個頂點均鄰接頂點子集V2中所有的頂點，此時則稱圖G 為完全二部圖，如圖3 所示.

圖3: 完全二部圖

定理2若圖G 是一個階為n ≥3 的完全二部圖，則γStR(G)≤.

證明 令|V1|=p, |V2|=q 且p ≥q.根據(jù)假設可知?=p 和n=p+q.下面分4 種情形來討論.

情形1n=3.

顯然有p=2, q =1 且?=2.根據(jù)定理1 可知γStR(G)≤成立.

情形2n=4.

情形2.2 當p = 3, q = 1 時，則?= 3 = n ?1，由定理1 可知γStR(G) ≤成立.

情形3n=5.

情形3.1 當p = 3, q = 2 時，則?= 3.假設頂點v ∈V2是圖G 中度數(shù)最大的頂點，即d(v) = ?(G).在圖G 的頂點集合V(G)上定義一個函數(shù)f : V(G) →{0,1,··· ,+ 1}，令f(v) =+ 1，而對所有與頂點v 鄰接的頂點x ∈N(v)，都有f(x) = 0，剩余結(jié)點f(w) = 1.顯然，函數(shù)f 是圖G 的頂點集合V(G)上的一個強羅馬控制函數(shù)，因此有

情形3.2 當p = 4, q = 1，此時?= 4 = n ?1.根據(jù)定理1 可知γStR(G) ≤成立.

情形4n ≥6.

在圖G 的頂點集合V(G)上定義一個函數(shù)f :V(G)→{0,1,··· ,+1}，令

其中v1∈V1, v2∈V2，剩余結(jié)點f(w) = 0.函數(shù)f 是圖G 頂點集合V(G)上的一個強羅馬控制函數(shù)，因此有

假設Kz是一個z 階完全圖，a1,a2,··· ,az是正整數(shù)且a1≥a2≥···≥az≥1.通過在完全圖的每個頂點處分別添加a1,a2,··· ,az個懸掛邊可得到完全圖的刺圖，記做.我們對圖中的結(jié)點進行標記，圖4 展示了完全圖K3的刺圖的頂點標記規(guī)則.

圖4: 完全圖K3 的刺圖

定理3若是一個階n ≥3 的完全圖Kz的刺圖，則γStR()≤.

情形1a1=a2=···=az=1.

在這種情形下，圖K?z的階和最大度分別對應為n = 2z 和?= z.在圖的頂點集合V()上定義一個函數(shù)f :V()→{0,1,··· ,+1}，選取圖中任意一個非葉子頂點v ∈V(K)，令f(v) =+1，而對所有與頂點v 相鄰接的頂點x ∈N(v)，有f(x) = 0，使得剩余結(jié)點均滿足f(w) = 1.根據(jù)強羅馬控制函數(shù)函數(shù)的定義可知，函數(shù)f 是圖的頂點集合V()上的一個強羅馬控制函數(shù)，因此有

情形2ai≥2，其中i=1,2,··· ,z.

情形3a1=a2=···=ak=2, ak+1=···=az=1，其中1 ≤k ≤z ?1.

假設頂點v1鄰接兩個懸掛邊.在圖K?z的頂點集合V(K?z)上定義一個函數(shù)f :V() →{0,1,··· ,+ 1}，令f(v1) =+ 1，而對所有與頂點v1相鄰接的頂點x ∈N(v1)，均有f(x) = 0，其他剩余結(jié)點f(w) = 1.顯而易見，f 是圖K?z的一個強羅馬控制函數(shù)，因此有

情形4a1≥3, a2≥3, ··· , ak≥3, ak+1=···=az=1，其中2 ≤k ≤z ?1.

情形4.1 當2 ≤k ≤3 時，在圖的頂點集合V()上定義一個函數(shù)f :V()→{0,1,··· ,+1}，令f(v1)=+1，而對所有與頂點v1相鄰接的頂點x ∈N(v1)，均有f(x) = 0，剩余結(jié)點f(w) = 1.函數(shù)f 是圖頂點集合V()上的一個強羅馬控制函數(shù)，因此有

因為

情形4.2 當4 ≤k ≤z ?1 時，在圖Kz?的頂點集合V(Kz?)上定義一個函數(shù)f :V()→{0,1,··· ,+1}，令

對所有x ∈N(v1)∪N(v2)∪···∪N(vk)?{v1,v2,··· ,vk}，均有f(x)=0，其他剩余結(jié)點f(w)=1.顯然，函數(shù)f 是圖K?z頂點集合V(K?z)上的一個強羅馬控制函數(shù)，因此有

因為