雙羅馬控制數的界

張 寧，葉淼林，肖鳳茹①

（安慶師范大學 數理學院，安徽 安慶 246133）

0 引言

近年來，隨著應用數學廣泛發展，控制的實際應用問題備受關注，如國際象棋問題、軍事防御問題等［1-2］?？刂评碚撟鳛閳D論研究的一個重要領域，可用來刻畫圖的若干性質，在不同條件下，控制衍生出的形式各有不同，如：符號控制［3］、意大利控制［4］、羅馬控制［5］、雙羅馬控制［6］等。圖的雙羅馬控制是圖論研究領域的熱點話題之一，涌現出許多豐富的結論和成果［7-10］，使控制領域逐步成為體系完整、內容充實的重要分支。

雙羅馬控制是在羅馬控制的基礎上進一步完善得到。羅馬帝國的城市中，如果一個沒有軍團保護的城市被攻擊，則該城市必須在至少一個駐扎著2個軍團的城市附近，這樣2個軍團中一個可以被派去保衛被攻擊的城市，受保衛羅馬帝國的防御策略影響，在文獻［2］中，Stewart最先定義和討論羅馬控制，該控制嚴重增加國防開支，故需要一個更有效精簡的控制策略，隨即引入雙羅馬控制。文獻［6］通過改進羅馬防御戰略，首次給出雙羅馬控制數學定義，建立雙羅馬控制數與控制數、羅馬控制數之間的關系，并根據圖G的階數，給出連通圖G的雙羅馬控制數的上界，刻畫達到這個上界的圖類。文獻［11］計算出路和圈的雙羅馬控制數的精確值，證明二部圖和弦圖相關的決策問題是np完備的，部分回答文獻［6］中的開放問題。文獻［12］給出的上下界。文獻［13］確定一些特殊圖的雙羅馬控制數，描述具有特定雙羅馬控制數的圖。文獻［14］繼續討論得出的上界和下界。文獻［15］利用最小度、頂點數、周長及圍長等圖論參數，研究給出雙羅馬控制數的若干上下界。

在此基礎上，本文繼續研究雙羅馬控制數的相關性質與結論。首先考慮具有函數的圖G，給出賦值為2的頂點個數滿足的條件，并得到樹T中葉子點和支撐點的1個賦值特點。隨后引入參數：最大度、意大利控制數、最小覆蓋數、打包數、3-彩虹控制數［16］，將參數的特性與雙羅馬控制結合，給出雙羅馬控制數的幾個界限，拓展雙羅馬控制的結論，完善控制理論結構體系，豐富代數圖論中對于雙羅馬控制研究。

1 預備知識

本文研究有限無向的簡單圖，設G的頂點集為V(G)，邊集為E(G)，簡記為G=(V,E)。G的階 |V|和邊數 |E|分別用n和m表示。對于頂點v∈V，開鄰域N(v)={u∈V:uv∈E} ，閉鄰域N[v]=N(v)?{v} 。頂點v的度degG(v)=|N(v)|，圖G的最大度為Δ(G)，最小度為δ(G)，度為0的點稱為孤立點。圖G的分支數用w(G)表示，若G的分支數只有1個，即w(G)=1，則稱圖G是連通的，否則稱G是不連通的。度為1的點稱為葉子點，與葉子點相鄰的點稱為支撐點，記L(G)為G中所有葉子點構成的集合，記S(G)為G中所有支撐點構成的集合。如果V(H)?V(G)，E(H)?E(G)，則稱H是G的子圖，滿足V(H)=V(G)的子圖H稱為G的生成子圖。無圈的連通圖稱為樹，若G的生成子圖是樹TG，則稱TG為G的生成樹。頂點數為n的路記作Pn，長為n的圈記作Cn。

設M?E(G)，對任意的e1,e2∈M，均有e1和e2不相鄰，則稱M為圖G的匹配。若G不存在匹配M′，使得 |M′|＞|M|，則稱M為G的最大匹配。最大匹配的基數稱為最大匹配數，記作α(G)。設K?V(G)，若G的每條邊都至少有1 個頂點在K中，則稱K為圖G的1 個覆蓋。若G不存在覆蓋K′，使得|K′|＜|K|，則稱K為G的最小覆蓋。最小覆蓋的基數稱為最小覆蓋數，記作β(G)。設R?V(G)，如果對于任意不同的2個頂點x,y∈R，均有N[x] ?N[y] =?，則稱R是圖G的1個打包集。若G不存在打包集R′，使得 |R′|＞|R|，則稱R為G的最大打包集。最大打包集的基數稱為打包數，記作ρ(G)。

本文主要運用幾個控制函數及與之對應的控制數概念，定義如下：

定義1［3］設S?V是G的1個頂點子集，如果S的閉鄰域滿足N[S]=V，則S中的點控制G，稱S為G的控制集。進一步，如果不存在G的控制集S′，使得 |S′|＜|S|，則S是圖G的最小控制集，S中的頂點個數稱為控制數，記作γ(G)，S稱為G的γ-集。

定義2［4］設函數f:V(G)→{0 ,1,2} ，Vi={v∈V|f(v)=i} ，i=0,1,2 ，對于任意的v∈V，使得如果f(v)=0，則v必須有1個鄰點在V2中，或者至少有2個鄰點在V1中，則稱f是V到{0 ,1,2} 的意大利控制函數或者羅馬{2 }-控制函數，簡記為IDFf。函數f:V(G)→{0, 1,2} 和頂點V的劃分(V0,V1,V2)間存在一個一一對應關系，記作。意大利控制函數f的權表示所有頂點的賦值之和，即，如果不存在G的意大利控制函數f′，使得ω(f′)＜ω(f)，則ω(f)稱為圖G的意大利控制數，記作γ{R2}(G)，f稱為G的γ{R2}(G)-函數。

定義3［6］設函數f:V(G)→{0 ,1,2,3} ，Vi={v∈V|f(v)=i}，i=0,1,2,3，對于任意的v∈V，使得：

（1）如果f(v)=0，則頂點v必須至少存在2個鄰點在V2中，或者存在1個鄰點在V3中；

（2）如果f(v)=1，則頂點v必須至少存在1個鄰點在V2?V3中。

則f稱為圖G的雙羅馬控制函數，簡記為DRDFf。f:V→{0 ,1,2,3} 和頂點V的劃分(V0,V1,V2,V3)間存在一個一一對應關系，記作。雙羅馬控制函數的權，如果不存在G的雙羅馬控制函數f′，使得ω(f′)＜ω(f)，則ω(f)稱為圖G的雙羅馬控制數，記作γdR(G)，f稱為G的γdR(G)-函數。

引理1［6］圖G中，存在1個權為γdR(G)的雙羅馬控制函數f，使得賦值為1的頂點集為空集。

2 主要結果

首先給出具有γdR(G)-函數的圖G中頂點集的性質，并給出樹T中葉子點和支撐點的一個賦值特點。

性質1 設G是1個圖，對于任意的γdR(G)-函數

證明 由定義得：V2f?V3f是G的1個控制集，且V2f?V3f=?，則

性質2 設T是n階樹，n≥3，則：

證明 （1）Δ≤2，此時圖G為路或者圈。

情況1G=Pn

恰好有1個鄰點在R中，R中的每個點至少有δ個鄰點在A中，因此δ|R|≤ |A|，則

定義f:V(G)→{0 ,1,2,3} ，使得

顯然f是G的DRDF，所以

定理4 設G是一個連通圖，階數為n，邊數為m，則對于G的生成樹TG有γdR(G)≥γdR(TG)-m+n-1。

證明 如果G是一棵樹，m=n-1，結論顯然成立。如果G不是一棵樹，設C是G中的一個圈，f是G的γdR(G)-函數，因為在C中至少有1個點賦值為0，記作v，即f(v)=0，考慮以下2種情況：

情況1 在C中，記與v相鄰的其中1 點為w，且f(w)=0，此時設G′=G-vw，定義G′的DRDFg:V(G)→{0 ,1,2,3} ，g(x)=f(x)，?x∈V。

情況2 在C中，記與v相鄰的2 個點為w,z，且w,z賦值為2 或3，此時設G′=G-vz，定義G′的DRDFg:V(G)→{0 ,1,2,3} ，使得

因 此 構 造 出1 個 圖G′ ，令G′ 中 包 含 圈 的 個 數 為|C(G′) |，G中 包 含 圈 的 個 數 為|C(G)|，則|C(G′) |≤|C(G)|-1，且對于情況1、情況2 均有ω(g)≤ω(f)+1，重復上述構造G′的步驟，可得到圖G的一個生成樹TG，使得

化簡得γdR(G)≥γdR(TG)-m+n-1。

根據3-彩虹控制函數的定義，g是圖G的3RDF，則

證明 設Hf的頂點劃分π(Hf)={S1,S2,…,St} ，如果Hf是二部圖，則 |Xf|=0，由斷言1知結論成立。

假設Hf不是二部圖，則t≥3。定義函數g:V(G)→2{1,2,3}，使得：

顯然g是圖G的3RDF，且

3 結語

雙羅馬控制在刻畫圖的性質方面存在重要研究意義和價值，文章依據雙羅馬控制數的定義，描述其與圖論幾個重要參數之間的關系，比較雙羅馬控制數與這些參數之間的大小，充實圖的雙羅馬控制理論，如何說明這些界在什么條件達到等號成立的情況，需要繼續深入探索，對研究極圖方面有推廣作用。