周洋洋， 許 進(jìn)

(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院， 北京 100871)

若無特殊聲明，本文所涉及的圖皆指有限、簡單和無向圖.對(duì)于給定圖G，分別用V(G)和E(G)表示G的頂點(diǎn)集和邊集，G中所含頂點(diǎn)數(shù)(|V(G)|)和邊數(shù)(|E(G)|)分別稱為G的階和規(guī)模.對(duì)任意v∈V(G)，v的開鄰域，記作N(v)，表示G中與頂點(diǎn)v相鄰的所有頂點(diǎn)構(gòu)成的集合，即N(v)={u|uv∈E(G)}.v的閉鄰域N[v]=N(v)∪{v}. 頂點(diǎn)v的度數(shù)，記作d(v)，是指N(v)中元素的個(gè)數(shù).用δ(G)和Δ(G)分別表示G的最小度和最大度，并分別簡記為δ和Δ. 設(shè)v∈V(G)，S?V(G)，如果v與S中的每個(gè)頂點(diǎn)都相鄰，則稱v控制S，也稱S被v控制.令S是G的一個(gè)頂點(diǎn)子集，如果S中任意兩個(gè)頂點(diǎn)在G中均不相鄰，則稱S為G的一個(gè)獨(dú)立集.若V′?V，E′?E，且E′中每條邊的兩個(gè)端點(diǎn)均在V′中，則稱圖H=(V′,E′)是圖G的一個(gè)子圖.設(shè)H是G的一個(gè)子圖，如果V(H)=V(G)，則稱H是G的生成子圖.如果對(duì)于子圖H中任意兩個(gè)頂點(diǎn)u和v、u、v在G中相鄰當(dāng)且僅當(dāng)它們?cè)贖中相鄰，則稱H為G的一個(gè)由V′導(dǎo)出的子圖，記為G[V′].用Pn=v1v2…vn-1vn表示n個(gè)頂點(diǎn)，長度為n-1的路，并用Cn=v1v2…vn-1vnv1表示n個(gè)頂點(diǎn)，長度為n的圈，常將長度為n的圈稱為n-圈.文中未說明的概念及記號(hào)，可參見文獻(xiàn)[1].

圖G=(V,E)的一個(gè)正常k-頂點(diǎn)著色，是指從頂點(diǎn)集V到顏色集{1,2,…,k}的一個(gè)映射f，使得G中任意兩個(gè)相鄰的頂點(diǎn)都著不同顏色.事實(shí)上，圖的k-頂點(diǎn)著色問題等價(jià)于將頂點(diǎn)集V(G)劃分為k個(gè)獨(dú)立集{V1,V2,…,Vk}，其中Vi={x∈V|f(x)=i}，i=1,2,…,k. 筆者將著相同顏色的頂點(diǎn)的集合稱為一個(gè)色組.圖G的色數(shù)，記作(G)，是G的一個(gè)正常著色所需顏色數(shù)的最小值.一個(gè)(G)-著色是G的具有最小基數(shù)的頂點(diǎn)著色.

圖G的一個(gè)控制集是指一個(gè)頂點(diǎn)子集S，使得G中每個(gè)頂點(diǎn)要么在S中，要么與S中的頂點(diǎn)相鄰.圖G的控制數(shù)，記作γ(G)，是指G的一個(gè)控制集的最小基數(shù).

圖的著色理論和控制理論是圖論中兩個(gè)非常活躍的重要領(lǐng)域，都有著廣泛豐富的研究成果，分別詳見文獻(xiàn)[2-9].此外，許多學(xué)者從多個(gè)方面討論了這兩個(gè)領(lǐng)域之間的聯(lián)系，并提出了一些新的概念.

2004年，Chellali等[10]展示了圖的色數(shù)與一些控制參數(shù)之間的關(guān)系.Cockayne等（1）Cockayne E,Hedetniemi S,Hedetniemi S M, et al. Dominator partitions of graphs, Unpublished manuscript, 1979.在1979年引入并介紹了圖的控制劃分的概念，在此推動(dòng)下，2006年，Gera等[11]提出了控制著色的概念.

圖的控制著色是一個(gè)正常頂點(diǎn)著色，使得每個(gè)頂點(diǎn)都控制至少一個(gè)色組(可能是頂點(diǎn)自身所構(gòu)成的色組).圖的控制著色數(shù)，記作d(G)，是指圖G的一個(gè)控制著色中色組的最小值.

在控制著色的基礎(chǔ)上，Kazemi[12]在2015年提出了全控制著色的概念，全控制著色是指一個(gè)正常頂點(diǎn)著色，使得每個(gè)頂點(diǎn)都與某個(gè)色組中的所有頂點(diǎn)相鄰.關(guān)于控制著色和全控制著色的更多結(jié)論，參見文獻(xiàn)[13-21].

2015年，Merouane等[22]提出了受控著色的概念.圖的受控著色是一個(gè)正常頂點(diǎn)著色，使得每個(gè)色組都被至少一個(gè)頂點(diǎn)控制.圖的受控著色數(shù)，記作dom(G)，是指圖G的一個(gè)受控著色所需顏色數(shù)的最小值.

基于控制著色和受控著色的研究，筆者在文獻(xiàn)[23]中提出了統(tǒng)治著色的概念，并研究得到了一些基本性質(zhì)和結(jié)論.

圖的統(tǒng)治著色，是指一個(gè)正常頂點(diǎn)著色，使得每個(gè)頂點(diǎn)都控制至少一個(gè)色組(可能是頂點(diǎn)自身所構(gòu)成的色組)，且每個(gè)色組都被至少一個(gè)頂點(diǎn)控制.圖的統(tǒng)治著色數(shù)，記作dd(G)，是指圖G的一個(gè)統(tǒng)治著色所需顏色數(shù)的最小值.

基于上述概念，學(xué)者們自然地關(guān)注了另一個(gè)有趣的問題：當(dāng)對(duì)圖G實(shí)施某些運(yùn)算時(shí)，這些參數(shù)會(huì)發(fā)生什么變化？針對(duì)這個(gè)問題，Ghanbari等[24]在2016年研究了某些運(yùn)算對(duì)全控制著色數(shù)的影響.2018年，Alikhani等[25]討論了一個(gè)圖的k-細(xì)分圖的全控制著色數(shù).2019年，Alikhani等[26]在研究幾類特殊圖的受控著色數(shù)的同時(shí)，還討論了它們的受控穩(wěn)定臨界數(shù)，即使得受控著色數(shù)dom(G)改變所需刪除的頂點(diǎn)(邊)數(shù)的最小值.同年，筆者在文獻(xiàn)[27]中研究了一些圖運(yùn)算對(duì)統(tǒng)治著色數(shù)的影響.

1 刪除頂點(diǎn)和邊

頂點(diǎn)和邊的移除是圖運(yùn)算中最基本的運(yùn)算，本節(jié)討論刪除頂點(diǎn)和刪除邊運(yùn)算對(duì)圖的受控著色數(shù)dom(G)的影響.

設(shè)v是G中任意頂點(diǎn)，e是G中任意一條邊.G-v是通過在圖G中刪除頂點(diǎn)v以及所有與v相關(guān)聯(lián)的邊所得到的圖.G-e是通過在G中刪除邊e所得到的圖.

定理1 設(shè)G是一個(gè)連通圖，v∈V(G)且v不是割點(diǎn)，則

dom(G)-1≤dom(G-v)≤dom(G)+d(v)-1.

證明先證明左邊不等式.給定G-v的任意受控著色，考慮G的受控著色如下：在G-v中添加頂點(diǎn)v和所有相應(yīng)的邊，給頂點(diǎn)v著一種新的顏色i，其他頂點(diǎn)著色不變.頂點(diǎn)v所在的色組可被v的任意一個(gè)鄰點(diǎn)控制，而其他色組仍由原來的頂點(diǎn)控制，這樣得到了圖G的一個(gè)受控著色.于是，dom(G)≤dom(G-v)+1.

下面證明右邊部分.對(duì)于圖G的任一受控著色，假設(shè)頂點(diǎn)v著顏色i，則有下面兩種情況：

情況(1):存在其他頂點(diǎn)著顏色i. 如果存在色組僅被頂點(diǎn)v控制，那么給此色組中的每個(gè)頂點(diǎn)一種新的顏色.顯然，至多有d(v)個(gè)這樣的頂點(diǎn).因?yàn)関不是割點(diǎn)，每一個(gè)新著色的頂點(diǎn)作為一個(gè)色組必然被其他鄰點(diǎn)(除v外)控制，而其他色組仍由原來的頂點(diǎn)控制.于是得到了G-v的一個(gè)受控著色，且dom(G-v)≤dom(G)+d(v)-1. 如果不存在上述性質(zhì)的色組，則由圖G原來的著色即可得到G-v的一個(gè)受控著色，且dom(G-v)≤dom(G).

情況(2):不存在其他頂點(diǎn)著顏色i. 按照情況(1)的分析，如果存在色組僅被頂點(diǎn)v控制，則dom(G-v)≤dom(G)+d(v)-2. 否則，dom(G-v)≤dom(G)-1.

定理得證.

定理2 設(shè)G是一個(gè)連通圖，e∈E(G)且e不是割邊，則

證明設(shè)e=uv∈E(G). 首先，證明左邊不等式.考慮G-e的一個(gè)受控著色，若在G-e中添加邊e，則存在兩種情況：

情況(1):頂點(diǎn)u和v在G-e的受控著色中著相同顏色.對(duì)u和v中之一著新的顏色i，其他頂點(diǎn)著色保持不變，這樣就得到了G的一個(gè)受控著色，且滿足dom(G)≤dom(G-e)+1.

情況(2):頂點(diǎn)u和v在G-e的受控著色中著不同顏色.那么，G-e的受控著色也是G的受控著色，于是dom(G)≤dom(G-e).

下面證明右邊不等式.考慮G的一個(gè)受控著色，假設(shè)u∈Vi，v∈Vj，即頂點(diǎn)u著顏色i，頂點(diǎn)v著顏色j. 于是，存在下面三種情況：

情況(1):頂點(diǎn)u不控制色組Vj，且頂點(diǎn)v不控制色組Vi. 在這種情況下，G的受控著色也是G-e的一個(gè)受控著色.從而，dom(G-e)≤dom(G).

情況(2):頂點(diǎn)u控制色組Vj，而頂點(diǎn)v不控制色組Vi. 根據(jù)定義，u與Vj中每個(gè)頂點(diǎn)都相鄰，而Vi必由其他頂點(diǎn)控制.在圖G-e中，給頂點(diǎn)v一種新的顏色k. 由于e不是割邊，G-e是連通圖且頂點(diǎn)v有其他鄰點(diǎn).那么，v自身構(gòu)成的色組必被其他鄰點(diǎn)控制，色組Vj{v}被頂點(diǎn)u控制，其他保持不變，這樣得到了G-e的一個(gè)受控著色，且dom(G-e)≤dom(G)+1.

情況(3):頂點(diǎn)u控制色組Vj，且頂點(diǎn)v控制色組Vi. 在這種情況下，給頂點(diǎn)u和v分別著新的顏色k和l. 由于e不是割邊，則G-e是連通圖.在新得到的著色中，頂點(diǎn)u和v各自所在的色組都會(huì)由它們其他的鄰點(diǎn)所控制.又因其他頂點(diǎn)著色不變，這個(gè)新得到的著色即是G-e的一個(gè)受控著色，且dom(G-e)≤dom(G)+2.

定理得證.

2 收縮頂點(diǎn)和邊

設(shè)圖G=(V,E)，S?V是一個(gè)頂點(diǎn)子集，在G中收縮S，記作G°S，是通過將S中的所有頂點(diǎn)替換為一個(gè)新的頂點(diǎn)，并將原來與S中頂點(diǎn)相關(guān)聯(lián)的邊均與這個(gè)新的頂點(diǎn)關(guān)聯(lián)所得到的圖.特別地，當(dāng)S={u,v}時(shí)，有下面兩種情況：

(1) 頂點(diǎn)u和v相鄰，即e=uv∈E(G). 在圖G中收縮邊e=uv，記作G°e，是通過刪除邊e，并將頂點(diǎn)u和v替換為一個(gè)新的頂點(diǎn)，使得原來與u或v相鄰的頂點(diǎn)均與這個(gè)新的頂點(diǎn)相鄰而得到的圖.收縮邊運(yùn)算，簡稱為縮邊運(yùn)算，如圖1所示，其中頂點(diǎn)周圍的黑色省略號(hào)標(biāo)記表示可能存在邊與該頂點(diǎn)關(guān)聯(lián).

圖1 縮邊運(yùn)算Fig.1 The edge contraction operation

(2)頂點(diǎn)u和v不相鄰.將此時(shí)的收縮運(yùn)算記作G° {u,v}，簡稱為縮點(diǎn)運(yùn)算，如圖2所示.

圖2 縮點(diǎn)運(yùn)算Fig.2 The vertex contraction operation

定理3 設(shè)G是一個(gè)連通圖，e∈E(G)，則

證明設(shè)e=uv∈E(G). 首先，證明左邊不等式.考慮G°e的一個(gè)dom(G°e)-受控著色.通過在G°e中添加刪除的頂點(diǎn)以及所有相應(yīng)的邊，得到圖G. 將e的端點(diǎn)的原來的著色刪除，并對(duì)頂點(diǎn)u和v分別著新的顏色k和l，其他頂點(diǎn)著色不變.易驗(yàn)證，這樣得到的是G的一個(gè)受控著色，且dom(G)≤dom(G°e)+2.

再證明右邊不等式.考慮G的一個(gè)dom(G)-受控著色f，其中f(u)=i，f(v)=j. 令x是替換u和v的新頂點(diǎn).下面構(gòu)造G°e的受控著色.給頂點(diǎn)x著新的顏色k，其他頂點(diǎn)著色不變.頂點(diǎn)x自身構(gòu)成的色組可由其任意鄰點(diǎn)控制，于是得到了G°e的一個(gè)受控著色，且dom(G°e)≤dom(G)+1.

定理得證.

定理4 設(shè)G是一個(gè)連通圖，u和v為G中任意兩個(gè)不相鄰的頂點(diǎn)，則

證明設(shè)u，v為G中任意兩個(gè)不相鄰的頂點(diǎn).首先,證明左邊不等式.考慮G° {u,v}的一個(gè)dom(G° {u,v})-受控著色.在G° {u,v}中添加刪除的頂點(diǎn)以及相應(yīng)的邊，得到圖G. 將u和v原來的顏色刪除，并分別給它們著新的顏色k和l，其他頂點(diǎn)著色不變.易驗(yàn)證，這是G的一個(gè)受控著色，且dom(G)≤dom(G° {u,v})+2.

接著，證明右邊不等式.考慮G的一個(gè)dom(G)-受控著色f，基于f來構(gòu)造G° {u,v}的受控著色.令x是替換u和v的新頂點(diǎn).給x著新的顏色k，其他頂點(diǎn)顏色保持不變.易驗(yàn)證，這樣得到的是圖G° {u,v}的一個(gè)受控著色，且dom(G° {u,v})≤dom(G)+1.

定理得證.

3 邊細(xì)分

設(shè)G是一個(gè)連通圖，k是一個(gè)正整數(shù).G的k-細(xì)分圖，記作Sk(G)，是通過將G中的每條邊替換成長度為k的路而得到的圖.對(duì)于每條邊e=vivj∈E(G)，用Pvivj表示替換vivj的k-路，并稱Pvivj為超邊，Pvivj的任意新頂點(diǎn)都是內(nèi)部頂點(diǎn).注意到，如果k=1，則S1(G)=G.

邊的細(xì)分是一種典型的圖運(yùn)算.本節(jié)研究一個(gè)圖G的k-細(xì)分圖的受控著色數(shù)，以及dom(G)和dom(Sk(G))之間的關(guān)系.

定理5 設(shè)G是一個(gè)含m條邊的連通圖，k≥2是正整數(shù)，則

(m-1)dom(Pk)+dom(Pk+1).

證明首先,證明左邊不等式.設(shè)e=uv為G中任意一條邊，Puv=ux1x2…xk-1v是Sk(G)中替換uv的路，如圖3所示.令f是Sk(G)的一個(gè)dom(Sk(G))-受控著色，考慮f在導(dǎo)出子圖Puv上的限制，記為f′. 由于f是受控著色，端點(diǎn)u(v)要么自身構(gòu)成色組，要么和其他頂點(diǎn)同在一個(gè)色組，都存在鄰點(diǎn)控制其所在色組，又因Puv內(nèi)部頂點(diǎn)的著色不變，那么f′的每個(gè)色組也必有頂點(diǎn)控制.因此，f′是Puv的一個(gè)受控著色，且dom(Pk+1)≤|f′|≤|f|=dom(Sk(G)).

圖3 邊細(xì)分運(yùn)算Fig.3 The edge subdivision operation

下面證明右邊不等式.設(shè)G是一個(gè)含m條邊的連通圖.對(duì)任意u∈V(G)，令N(u)={v1,v2,…,vp}，邊uvi分別由超邊Puvi替換，i=1,2,…,p.類似一般Pk+1的受控著色，可用dom(Pk+1)種顏色給超邊Puv1的頂點(diǎn)著色.對(duì)Puvi(i=1,2,…,p)的頂點(diǎn)著色，使得頂點(diǎn)u的著色唯一(即u在Puvi(i=2,…,p)中的著色均與Puv1中一致)，并且滿足

f(Puvi)∩f(Puvj){f(u)}=?，

其中,i,j=1,2,…,p，i≠j，f(Puvi)表示Puvi中頂點(diǎn)的顏色的集合.這樣，用至多(p-1)dom(Pk)+dom(Pk+1)種顏色得到了Puvi(i=1,2,…,p)的一個(gè)受控著色.接著，考慮與vi(i=1,2,…,p)相關(guān)聯(lián)的邊所對(duì)應(yīng)的未著色的超邊.繼續(xù)重復(fù)上述過程，直到Sk(G)的所有頂點(diǎn)均被著色.注意到，某些位于圈上的頂點(diǎn)會(huì)被重復(fù)著色，但這不會(huì)影響最后結(jié)果.容易驗(yàn)證，最后得到的著色是Sk(G)的一個(gè)受控著色，且使用了至多(m-1)dom(Pk)+dom(Pk+1)種顏色.因此，右邊不等式成立.

定理得證.

4 擴(kuò)圈運(yùn)算

本節(jié)討論擴(kuò)圈運(yùn)算，以及受控著色數(shù)在擴(kuò)圈運(yùn)算下的變化.

圖4 擴(kuò)圈運(yùn)算Fig.4 The cycle extending operation

定理6 設(shè)G是一個(gè)連通圖，C是G中任意長度為l(≥3)的圈，則

證明首先,證明右邊不等式.對(duì)于G的任意一個(gè)dom(G)-受控著色，給中心頂點(diǎn)x著一種新的顏色，而其他頂點(diǎn)顏色不變，這樣就得到了W+(G)的一個(gè)受控著色.因此，dom(W+(G))≤dom(G)+1.

接著，證明左邊不等式.設(shè)f是W+(G)的一個(gè)dom(W+(G))-受控著色，下面基于f構(gòu)造G的一個(gè)受控著色，在W+(G)中刪除頂點(diǎn)x及與它相關(guān)聯(lián)的邊，得到圖G. 需要考慮那些僅被頂點(diǎn)x控制的色組，顯然，這些色組中的元素只可能是圈C上的頂點(diǎn)，因此，只需添加至多l(xiāng)種新的顏色給這些頂點(diǎn)重新著色，就可得到G的一個(gè)受控著色.于是，dom(G)≤dom(W+(G))+l.

定理得證.

5 結(jié)論與展望