圖的全-Domination染色

王彩云

(青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西寧 810008)

1 引言與預(yù)備知識

圖G的一個正常點染色是一個映射f:V(G)→{1,…,k},使得圖G中的任意兩個相鄰頂點u,v均有f(u)≠f(v)。圖G的正常點染色所需要的最小顏色數(shù)稱為色數(shù),記為χ(G)。事實上,圖G的正常點染色可將圖G的頂點集劃分為k個獨立集{V1,V2,…,Vk},這里每個獨立集稱為一個色類,記為Vi={v∈V(G)|f(v)=i},i=1,…,k。圖G的一個l-染色是指用l種顏色對G進行的一個正常點染色。

圖的染色被大量用在涉及稀缺資源分配的實際問題的模型中(例如：課程表問題)，并且它在圖論、離散數(shù)學(xué)和組合優(yōu)化的發(fā)展中發(fā)揮了關(guān)鍵作用。隨著應(yīng)用背景的不斷拓寬,一些其他染色概念被提出來。

Gera[11]等人提出了圖的domiator染色的概念。圖的domiator染色是指圖G中每個頂點都至少與一個色類(可能是自己的色類)里的全部頂點相鄰。圖G的dominator染色所需的最少顏色數(shù)稱為G的dominator色數(shù),記為χd(G)。在2012年,K.Kavitha[12]研究了星和雙星圖族的 Middle圖、Total圖和Central圖的dominator色數(shù),同時還證明了上述圖族的dominator色數(shù)和星色數(shù)之間的關(guān)系。

周[15]等人在dominator染色概念的基礎(chǔ)上提出了domination染色的概念。圖G的domination染色是指G的每個頂點至少與一個色類里的全部頂點相鄰并且圖G的每個色類的頂點要與G中至少一個頂點相鄰。圖G的domination染色所需的最少顏色數(shù)稱為G的domination色數(shù),記為χdd(G)。

K.P.chithra[16]等人在dominaton染色概念的基礎(chǔ)上提出了全-do mination染色的概念。圖G的全-domination染色是指G的每個頂點至少與一個色類(除了v)里的全部頂點相鄰并且圖G的每個色類的頂點要與G中至少一個頂點相鄰。圖G的全-domination染色所需的最少顏色數(shù)目稱為G的全-domination色數(shù),記為χtd(G)。圖G的一個k-全-domination染色是指用k種顏色對G進行一個全-domination染色。K.P.chithra在文獻[16]中研究了路、圈、路的補圖和圈的補圖的全-domination色數(shù)并且得出樹的全-domination色數(shù)的上下界,同時刻畫了樹的全-domination染色數(shù)上下界相等時的充要條件。在2019年,周和趙[15]證明了對于任意圖G,χdd(G)=k(k∈N*)是NP-完全的。

本文證明了對于任意圖G,χtd(G)=k(k∈N*)是NP-完全的,并研究了χtd(G)和χtd(G′)之間的關(guān)系,這里G′是G通過某種操作得到的圖。

2 全-domination色數(shù)的NP-完全性

定理2.1當(dāng)k≥4時,任意一個圖G的k-全-domination色數(shù)是NP-完全的。

證明下面給出,圖G的一個k-全-domination染色與圖G′的一個(k+1)-染色是等價的。

事實上,設(shè)G=(V(G),E(G))是一個沒有孤立點的圖,圖G′是將圖G添加一個新的頂點x并且使得頂點x和圖G中的每個頂點都相連得到的圖。下面證明χ(G)=k?χtd(G′)=k+1。

(1)f′是正常點染色。

(2)圖G′中除了頂點x以外的每個頂點都可以控制顏色類Vk+1′,并且頂點x可以控制f的全部色類。

(3)圖G′中除了Vk+1′以外的每一個色類都是由頂點x控制,并且Vk+1′由圖G的任意一個頂點控制。

由上可知,當(dāng)k≥4時,k-全-domination染色問題是NP-完全的。

3 圖G-v和G-e的全-domination色數(shù)

下面研究從圖G中刪除一個頂點或一條邊之后圖的全-domination色數(shù)。

設(shè)v∈V(G),圖G-v是從圖G中刪除頂點v得到的圖。

定理3.1設(shè)G是連通圖,v∈V(G)且不是割點,則χtd(G)-2≤χtd(G-v)≤χtd(G)+deg(v)-1。

證明設(shè)u,v∈V(G)且uv∈E(G),f:V(G)→{1,…,k}是圖G-v的一個全-domination染色。下面對圖G進行正常染色:用兩種顏色m,n(m≠n?{1,…,k})分別對頂點u和v進行染色,圖G中其余頂點的染色方式是f在G-v上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色。因此,χtd(G)-2≤χtd(G-v)。

接下來證明χtd(G-v)≤χtd(G)+deg(v)-1。設(shè)f:V(G)→{1,…,k}是圖G的一個全-domination染色,且f(v)=i。下面對圖G-v進行染色:

情形1圖G中僅有頂點v染i色。

用deg(v)種顏色i和cj(j=1,…,deg(v)-1,cj?{1,…,k})對頂點v的開鄰域進行染色,圖G-v中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G-v的一個全-domination染色,因此χtd(G-v)≤χtd(G)+deg(v)-1。

情形2圖G中除了頂點v,還有其他頂點染i色。

圖G-v的頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G-v的一個全-domination染色,有χtd(G-v)≤χtd(G)。

通過情形1和情形2,因此,χtd(G-v)≤χtd(G)+deg(v)-1。

根據(jù)定理3.1,可以得到下面的推論:

推論3.2設(shè)G是連通圖,v∈V(G)且不是割點,那么|χtd(G)-χtd(G-v)可以任意大。

設(shè)e=uv∈E(G),圖G-e是從圖G中刪除邊e得到的圖。

定理3.3設(shè)G是連通圖,若e=uv∈E(G)且不是割邊,則χtd(G)-1≤χtd(G-e)≤χtd(G)+2。

證明首先證明χtd(G)-1≤χtd(G-e)。設(shè)f:V(G)→{1,…,k}是圖G-e的一個全-domination染色,下面對圖G進行染色:

情形1若f(v)=f(u)=i(i∈{1,…,k})。

用顏色j(j?{1,…,k})對頂點u或v進行染色,圖G中其余頂點的染色方式是f在G-e上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色,因此有χtd(G)-1≤χtd(G-e)。

情形2若f(v)=i,f(u)=j(i≠j∈{1,…,k})。

圖G中頂點的染色方式是f在G-e上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色,所以χtd(G)≤χtd(G-e)。

通過情形1和情形2,有χtd(G)-1≤χtd(G-e)。

接著證明χtd(G-e)≤χtd(G)+2。設(shè)f:V(G)→{1,…,k}是圖G的一個全-domination染色,f(u)=i和f(v)=j(i≠j∈{1,…,k})。下面對圖G-e進行染色：

情形1頂點v控制色類Vi且頂點u控制色類Vj。

用兩種顏色m,n(m≠n?{1,…,k})分別對點u的鄰點s和點v的鄰點w進行染色,并且圖G-e中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G-e的一個全-domination染色,因此χtd(G-e)≤χtd(G)+2。

情形2頂點v控制色類Vi且頂點u不控制色類Vj。

用顏色m(m?{1,…,k})對頂點u的鄰點w進行染色,并且圖G-e中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G-e的一個全-domination染色,因此χtd(G-e)≤χtd(G)+1。

情形3頂點v不控制色類Vi且頂點u控制色類Vj,與情況(2)的證明過程類似。

綜上所述,χtd(G-e)≤χtd(G)+2。

上述兩個定理分別得出了對圖G刪除一個點或一條邊的簡單操作后的圖的全-domination色數(shù),下面研究對圖G進行收縮頂點集(邊)和圈擴展后的圖的全-domination色數(shù)。

4 圖Gv，G{u,v},Ge，G⊙v和W+(G)的全-domination色數(shù)

設(shè)v∈V(G),圖Gv是從G中刪除頂點v使得頂點v的鄰點兩兩連接形成的圖。設(shè)S={u,v}?V(G)，圖GS是從G中刪除頂點v和頂點u后加入一個新的頂點x并且頂點x與頂點v和頂點u的鄰點均相鄰形成的圖。圖GS有兩種情形:(1)頂點u和v是相鄰的,不妨假設(shè)e=uv∈E(G),記為圖Ge。(2)頂點u和v是不相鄰的,記為G{u,v}。圖G⊙v是圖G刪除頂點v的鄰域中頂點對之間的邊而得到的圖,注意頂點v并沒有從圖G中移除。對于含圈的連通圖G,C是G中的一個長度為l(≥3)的圈。圖W+(G)是從圖G中添加一個新的頂點x并且在頂點x與圈C上的每個頂點之間加入一條新邊得到的圖。上述圖,參看圖4-1：

圖1 圖例

定理4.1設(shè)G是連通圖且v∈V(G),則χtd(G)-2≤χtd(Gv)≤χtd(G)+deg(v)。

證明首先證明χtd(Gv)≤χtd(G)+deg(v)。設(shè)f:V(G)→{1,…,k}是圖G的一個全-domination染色。下面對圖Gv進行染色,用deg(v)種顏色cj(cj?{1,…,k})(j=1,…,deg(v))對頂點v的開鄰域進行染色,并且圖Gv中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖Gv的一個全-domination染色,因此χtd(Gv)≤χtd(G)+deg(v)。

下面證明χtd(G)-2≤χtd(Gv)。設(shè)f:V(G)→{1,…,k}是圖Gv的一個全-domination染色。對圖G進行染色,用兩種顏色m,n(m≠n?{1,…,k})分別給頂點v和其鄰點u染色,并且圖G中其余頂點的染色方式是f在Gv上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色,因此χtd(G)-2≤χtd(Gv)。

根據(jù)定理3.1和定理4.1,可以得到下面的推論:

推論4.2設(shè)G是連通圖,v∈V(G)且不是割點。則

定理4.3設(shè)G是連通圖,則χtd(G)-2≤χtd(G{u,v})≤χtd(G)+4。

證明證明χtd(G)-2≤χtd(G{u,v})。設(shè)f:V(G)→{1,…,k}是圖G一個全-domination染色,下面對圖G{u,v}進行染色:用兩種顏色m,n(m≠n?{1,…,k})分別對頂點x和其鄰點w進行染色,圖G{u,v}中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G{u,v}的一個全-domination染色,因此,χtd(G)-2≤χtd(G{u,v})。

接下來證明χtd(G{u,v})≤χtd(G)+4。 設(shè)f:V(G)→{1,…,k}是圖G{u,v}的一個全-domination染色,下面對圖G進行染色:

情形1圖G{u,v}中僅有頂點x染i色。

頂點u染i色并用三種顏色m,n,l(m≠n≠l?{1,…,k})對頂點v、頂點u和頂點v的一個鄰點w進行染色。圖G中其余頂點的染色方式是f在G{u,v}上的限制,根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色。因此,χtd(G{u,v})≤χtd(G)+3。

情形2圖G{u,v}除了頂點x以外,還有其他頂點染i色。

用四種顏色m≠n≠l≠q(m,n,l,q?{1,…,k})對頂點u及其一個鄰點和頂點v及其一個鄰點進行染色。圖G中其余頂點的染色方式是f在G{u,v}上的限制,根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色。因此,χtd(G{u,v})≤χtd(G)+4。

接下來考慮頂點u和v在G中是相鄰的,即e=uv∈E(G)的情形。

定理4.4設(shè)G是連通圖且e=uv∈E(G),則χtd(G)-2≤χtd(Ge)≤χtd(G)+1。

證明首先證明χtd(Ge)≤χtd(G)+1。設(shè)f:V(G)→{1,…,k}是圖G的一個全-domination染色,使得f(u)=i和f(v)=j。下面給圖Ge進行染色:

情形1若頂點u和頂點v都是單色類并且頂點u控制色類Vj和頂點v控制色類Vi。

頂點x染i色并且點x的一個鄰點s染j色,圖Ge中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖Ge的全-dom ination染色,有χtd(Ge)≤χtd(G)。

情形2若頂點u不是單色類,頂點v是單色類并且頂點u控制色類Vj。

頂點x染j色并用顏色m(m?{1,…,k})對點x的一個鄰點s進行染色,圖Ge中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖Ge的全-domination染色,有χtd(Ge)≤χtd(G)+1。

情形3若頂點v不是單色類,頂點u是單色類并且頂點v控制色類Vi。證明過程與情況(2)的類似。

根據(jù)情形1、2和3,有χtd(Ge)≤χtd(G)+1。

現(xiàn)在證明χtd(G)-2≤χtd(Ge)。設(shè)f:V(G)→{1,…,k}是圖Ge的任意一個全-domination染色。用兩種顏色m,n(m≠n?{1,…,k})對頂點u和頂點v進行染色并且圖G中其余頂點的染色方式是f在Ge上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色,因此χtd(G)-2≤χtd(Ge)。

根據(jù)定理3.3和定理4.4,可以得到下面的推論:

推論4.5設(shè)G是連通圖且e∈E(G)不是割邊。那么

定理4.6設(shè)G是連通圖且v∈V(G),則χtd(G)-deg(v)-1≤χtd(G⊙v)≤χtd(G)+1。

證明首先證明χtd(G⊙v)≤χtd(G)+1。設(shè)f:V(G)→{1,…,k}是圖G的一個全-domination染色,且f(v)=i,下面給圖G⊙v進行染色:

情形1圖G中除了頂點v以外,還有其他頂點染i色。

用顏色m(m?{1,…,k})對染i色的頂點(除了v)進行染色,圖G⊙v中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G⊙v的一個全-domination染色,因此χtd(G⊙v)≤χtd(G)+1。

情形2圖G中僅有頂點v染i色。

圖G⊙v的頂點染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G⊙v的一個全-domination染色,因此χtd(G⊙v)≤χtd(G)。

因此,χtd(G⊙v)≤χtd(G)+1。

現(xiàn)在證明χtd(G)-deg(v)-1≤χtd(G⊙v)。設(shè)f:V(G)→{1,…,k}是圖G⊙v的一個全-domination染色,下面給圖G進行染色。用deg(v)+1種顏色cj(cj?{1,…,k}),(j=1,…,deg(v)+1)對頂點v的閉鄰域染色,根據(jù)全-domination染色的定義,這種染色是圖G的全-domination染色。所以χtd(G)-deg(v)-1≤χtd(G⊙v)。

根據(jù)定理4.6,可以得出下面的推論:

推論4.7設(shè)G是連通圖且v∈V(G),則|χtd(G)-χtd(G⊙v)|可以任意大。

定理4.8設(shè)G是連通圖,Cl是G中的長度為l的圈,則χtd(G)-l+1≤χtd(W+(G))≤χtd(G)+1。

證明首先證明χtd(W+(G))≤χtd(G)+1。設(shè)f:V(G)→{1,…,k}是圖G的全-domination染色,下面對圖W+(G)進行染色。用顏色m(m?{1,…,k})對頂點x染色,圖W+(G)中其余頂點的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖W+(G)的全-domination染色,因此χtd(W+(G))≤χtd(G)+1。

現(xiàn)在證明χtd(G)-l+1≤χtd(W+(G))。設(shè)f:V(G)→{1,…,k}是W+(G)的一個全-domination染色。下面給圖G的頂點進行染色:

情形1圖W+(G)中僅有頂點x染i色。

因為圖W+(G)中僅有頂點x染i色,用顏色i和l-1種顏色m(m?{1,…,k})(m=1,…,l-1)對圈Cl上的l個頂點進行染色,圖G中其余頂點的染色方式是f在W+(G)上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色。因此,χtd(G)-l+1≤χtd(W+(G))。

情形2圖W+(G)中除了頂點x以外,還有其他頂點染i色。

用Vi表示所有染i色的頂點集合,下面給圖G進行染色。用l種顏色cj(cj?{1,…,k})(j=1,…,l)對圈C上的頂點進行染色。圖G中其余頂點的染色方式是f在W+(G)上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個全-domination染色。

因此,χtd(G)-l≤χtd(W+(G))。