王彩云

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理3.1設(shè)G是連通圖,v∈V(G)且不是割點(diǎn),則χ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的一個(gè)全-domination染色。下面對(duì)圖G進(jìn)行正常染色:用兩種顏色m,n(m≠n?{1,…,k})分別對(duì)頂點(diǎn)u和v進(jìn)行染色,圖G中其余頂點(diǎn)的染色方式是f在G-v上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個(gè)全-domination染色。因此,χtd(G)-2≤χtd(G-v)。

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

情形1圖G中僅有頂點(diǎn)v染i色。

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

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

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

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

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

推論3.2設(shè)G是連通圖,v∈V(G)且不是割點(diǎn),那么|χ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的一個(gè)全-domination染色,下面對(duì)圖G進(jìn)行染色:

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

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

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

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

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

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

情形1頂點(diǎn)v控制色類Vi且頂點(diǎn)u控制色類Vj。

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

情形2頂點(diǎn)v控制色類Vi且頂點(diǎn)u不控制色類Vj。

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

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

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

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

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

設(shè)v∈V(G),圖Gv是從G中刪除頂點(diǎn)v使得頂點(diǎn)v的鄰點(diǎn)兩兩連接形成的圖。設(shè)S={u,v}?V(G)，圖GS是從G中刪除頂點(diǎn)v和頂點(diǎn)u后加入一個(gè)新的頂點(diǎn)x并且頂點(diǎn)x與頂點(diǎn)v和頂點(diǎn)u的鄰點(diǎn)均相鄰形成的圖。圖GS有兩種情形:(1)頂點(diǎn)u和v是相鄰的,不妨假設(shè)e=uv∈E(G),記為圖Ge。(2)頂點(diǎn)u和v是不相鄰的,記為G{u,v}。圖G⊙v是圖G刪除頂點(diǎn)v的鄰域中頂點(diǎn)對(duì)之間的邊而得到的圖,注意頂點(diǎn)v并沒有從圖G中移除。對(duì)于含圈的連通圖G,C是G中的一個(gè)長(zhǎng)度為l(≥3)的圈。圖W+(G)是從圖G中添加一個(gè)新的頂點(diǎn)x并且在頂點(diǎn)x與圈C上的每個(gè)頂點(diǎn)之間加入一條新邊得到的圖。上述圖,參看圖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的一個(gè)全-domination染色。下面對(duì)圖Gv進(jìn)行染色,用deg(v)種顏色cj(cj?{1,…,k})(j=1,…,deg(v))對(duì)頂點(diǎn)v的開鄰域進(jìn)行染色,并且圖Gv中其余頂點(diǎn)的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖Gv的一個(gè)全-domination染色,因此χtd(Gv)≤χtd(G)+deg(v)。

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

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

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

定理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一個(gè)全-domination染色,下面對(duì)圖G{u,v}進(jìn)行染色:用兩種顏色m,n(m≠n?{1,…,k})分別對(duì)頂點(diǎn)x和其鄰點(diǎn)w進(jìn)行染色,圖G{u,v}中其余頂點(diǎn)的染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G{u,v}的一個(gè)全-domination染色,因此,χtd(G)-2≤χtd(G{u,v})。

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

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

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

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

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

接下來(lái)考慮頂點(diǎn)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的一個(gè)全-domination染色,使得f(u)=i和f(v)=j。下面給圖Ge進(jìn)行染色:

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

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

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

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

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

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

現(xiàn)在證明χtd(G)-2≤χtd(Ge)。設(shè)f:V(G)→{1,…,k}是圖Ge的任意一個(gè)全-domination染色。用兩種顏色m,n(m≠n?{1,…,k})對(duì)頂點(diǎn)u和頂點(diǎn)v進(jìn)行染色并且圖G中其余頂點(diǎn)的染色方式是f在Ge上的限制。根據(jù)全-domination染色的定義,這種染色是圖G的一個(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的一個(gè)全-domination染色,且f(v)=i,下面給圖G⊙v進(jìn)行染色:

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

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

情形2圖G中僅有頂點(diǎn)v染i色。

圖G⊙v的頂點(diǎn)染色方式是f在G上的限制。根據(jù)全-domination染色的定義,這種染色是圖G⊙v的一個(gè)全-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的一個(gè)全-domination染色,下面給圖G進(jìn)行染色。用deg(v)+1種顏色cj(cj?{1,…,k}),(j=1,…,deg(v)+1)對(duì)頂點(diǎn)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中的長(zhǎng)度為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染色,下面對(duì)圖W+(G)進(jìn)行染色。用顏色m(m?{1,…,k})對(duì)頂點(diǎn)x染色,圖W+(G)中其余頂點(diǎn)的染色方式是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)的一個(gè)全-domination染色。下面給圖G的頂點(diǎn)進(jìn)行染色:

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

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

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

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

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