圈與路的笛卡爾乘積圖的多彩染色

張春梅, 史雅馨, 杜伊諾

(新疆大學數(shù)學與系統(tǒng)科學學院，烏魯木齊 830017)

0 引言

圖論起源于1736 年，歐拉向圣彼得堡科學院遞交的論文《哥尼斯堡的七座橋》解答了七橋問題，并開創(chuàng)了數(shù)學一個新的分支—圖論與幾何拓撲。圖論中的四色問題已經(jīng)成為了近代三大數(shù)學難題之一，人類在尋找四色問題的答案的同時，推動了圖論的發(fā)展，尤其是對圖的染色理論、平面圖理論、代數(shù)拓撲等分支的發(fā)展起到了重要的推動作用。隨著圖論的發(fā)展，圖論理論逐漸成為離散數(shù)學中的重要知識之一。隨著圖論的發(fā)展更是被廣泛應用于社會生活的各個方面，比如交通規(guī)劃、經(jīng)濟分析、網(wǎng)絡通信等。圈和路是圖論研究中的重要對象，在圖論中占有非常重要的地位，其實際應用也越來越廣泛。高速數(shù)字計算機的發(fā)明，促使更多數(shù)學家對“四色問題”的研究。電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現(xiàn)，大大加快了對四色猜想證明的進程。1976 年6 月，美國數(shù)學家Appel 和Haken 與運用計算機的專家Kock 三人合作，在美國伊利諾斯大學兩臺不同的電子計算機上，用了1 200 個小時，作了100 億個判斷，結(jié)果沒有一張地圖是需要五色的，最終證明了四色定理[1]，轟動了世界。在日常生活中，很多優(yōu)化問題和網(wǎng)絡問題，諸如計算機網(wǎng)絡中的文件傳輸問題、時間表問題、信號發(fā)射問題等都涉及到圖的圈和路理論。本文主要對圈與路的笛卡爾積圖的多彩染色進行研究。

圖的r-多彩染色的另一個研究動機源于電力網(wǎng)絡最優(yōu)重新配置中多代理系統(tǒng)部署中的通信問題[2–5]。代理是一種能夠在該環(huán)境中自主行動以實現(xiàn)其設計目標的計算機系統(tǒng)。自治意味著環(huán)境功能中的組件完全受自己的控制。近年來，結(jié)合圖算法在電力網(wǎng)絡優(yōu)化重構(gòu)中使用多智能體系統(tǒng)已得到了廣泛應用。在電力網(wǎng)絡最優(yōu)重構(gòu)過程中部署的多智能體系統(tǒng)的圖建模中，形成圖模型來模擬智能體的通信和工作關(guān)系，其中智能體被建模為頂點，并且如果對應的智能體在兩個頂點相鄰工作中需要溝通。為了執(zhí)行最佳的重新配置，每個智能體需要從其相鄰智能體傳感器獲取特定但不同種類的信息，并使用這些信息做出自己的決策并采取行動。在建模中，代理以無線方式進行通信。每個代理可以接收不同頻率的信號，但只能有一個發(fā)射頻率。要求相鄰智能體必須具有不同的發(fā)射頻率，并且對于固定整數(shù)r> 0，每個智能體需要從其相鄰智能體接收至少r種不同的信息，這些信息通過其發(fā)射頻率來區(qū)分。這相當于要求每個代理必須至少使用r個不同發(fā)射頻率的鄰居。為了將發(fā)射頻率分配給代理，很自然地將其視為圖的r色調(diào)染色問題，其中發(fā)射頻率是顏色。

本文所研究的圖是簡單有限圖，E(G)和V(G)分別表示圖G的邊集和頂點集。在圖G中，頂點vi的度數(shù)(記為d(vi))是與其關(guān)聯(lián)的邊數(shù)，其中δ(G)和?(G)表示圖G中的最小和最大頂點度。記Pn為長度為n-1 的路，Cm為長度m個點的圈。圖G和H的笛卡爾乘積圖記為G□H，其頂點集為V(G)×V(H)，(u1,v1)與(u2,v2)相鄰當且僅當u1=u2,v1v2∈E(H)，或v1=v2,u1u2∈E(G)。圖G的正常頂點染色是映射c:V(G)→L，該映射具有性質(zhì)：如果u和v是相鄰的兩個點，則c(u)和c(v)是不同的。頂點k-染色是滿足|L| =k的正常頂點染色。使G具有頂點k-染色的最小整數(shù)k稱為G的色數(shù)，并用χ(G)表示。2001 年，Montgomery[6]首次提出了r-多彩染色的定義，并提出了如果對于每個度數(shù)至少為2 的頂點v和v的鄰點至少接收兩種不同的顏色，則一個正常的頂點k-染色稱為2-動態(tài)染色。使G具有2-動態(tài)染色的最小正整數(shù)k稱為圖G的2-動態(tài)色數(shù)，并用χ2(G)表示。此外，2-動態(tài)染色也被稱為動態(tài)染色。通常，如果對于度數(shù)至少為r的每個頂點v的鄰點至少接收r種不同的顏色，則正常的頂點k-染色稱為(k,r)-染色。使G具有(k,r)-染色的最小正整數(shù)k稱為G的r-多彩色數(shù)，并用χr(G)表示。

Lai 等人[7]證明了當n ≥3,r ≥2 時，n個頂點的圈Cn的多彩色數(shù)為

Lai 等人[8]證明了當G是一個連通圖時，有以下結(jié)論：

1) 如果G ?=C5, ?(G)≤3，則χ2(G)≤4；

2) 如果?(G)≥4，則χ2(G)≤?(G)+1。Akbari 等人[9]證明了對于自然數(shù)m和n(m,n ≥2)，有以下結(jié)論：

1) 如果m,n ≥2，則χ2(Pm□Pn)=4；

2) 如果m ≥3，則

Kang 等人[11]證明了對于自然數(shù)m和n(m,n ≥2)，有以下結(jié)論：如果mn ≡2(mod 4)，則χ3(Pm□Pn)=5。Suil[13]證明了對于自然數(shù)m,n ≥3，有以下結(jié)論：

1) 對于m ≤n(mod 4)，有

Lai 等人在文獻[7]中給出了χr(G)、?(G)以及|V(G)|的如下關(guān)系

在上述工作基礎上，本文研究圈和路的笛卡爾乘積圖的r-多彩色數(shù)。

1 圖Cm□Pn 的多彩色數(shù)

在本節(jié)中，我們一般將笛卡爾乘積圖G的染色表示為矩陣A，并定義c(ui,vj) =aij,A=[aij]m×n。

對于自然數(shù)m(m ≥3)和n(n ≥2)，V(Cm) ={u1,u2,···,um},V(Pm) ={v1,v2,···,vn}。Cm和Pn的笛卡爾乘積圖記為圖G，用G=Cm□Pn表示，其中V(G) ={(ui,vj)|ui ∈V(Cm),vj ∈V(Pn)}。

本文根據(jù)正整數(shù)m和n的取值不同，分類討論Cm□Pn的r-hued 色數(shù)。由于r=4 的證明過于繁瑣，在此不一一列出，只給出r=3 的情況的證明。當r=3 時，有如下結(jié)論。

定理1 對于任意兩個自然數(shù)m(m ≥3)和n(n ≥2)，有

證明 設V(Cm)={u1,u2,···,um},V(Pn)={v1,v2,···,vn}，并且G=Cm□Pn。由(1)式可知，χr(G)≥min{?(G),r}+1，故χ3(Cm□Pn)≥4。我們分以下三種情形進行討論。

情形1m ≡0(mod 4)。

當4|m時，給出一個(4,3)-染色

矩陣A從第3 列開始循環(huán)

因為對于任意一條邊uivj ∈E(Cm□Pn)，我有c(ui)?=c(vj)，所以按照Am×n的染色c是一個(4,1)-染色。下面證明c是一個(4,3)-染色：

i) 任選一個點(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n這樣染色，是一個(4,3)-染色，所以χ3(Cm□Pn)≤4。由(1)式可知χr(G)≥min{?(G),r}+1，故χ3(Cm□Pn)≥4。因此，χ3(Cm□Pn)=4。

情形2m=3 或m=6 且n=2k(k ≥1)或m ∈{7,11}且n ?=3k+1(k ≥1)，我們又可分以下四種情況進行討論。

情形2.1m=3，給出一個(6,3)-染色c，按照A3×n進行染色

矩陣A從第3 列開始循環(huán)

因為對于任意一條邊uivj ∈E(C3□Pn)，我們有c(ui)?=c(vj)，所以按照A3×n的染色c是一個(6,1)-染色。下面證明c是一個(6,3)-染色：

i) 任選一個點(ui,vk)∈V(C3□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC3□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NC3□Pn(ui,vk))|=3；

故按照A3×n這樣染色，是一個(6,3)-染色，所以χ3(C3□Pn)≤6。

接下來，用反證法證明χ3(C3□Pn)≥6。假設χ3(C3□Pn)≤5，對于第1 列和第2 列來說，因為點(u1,v1)、(u2,v1)和(u2,v1)在一個三角形中，我們不妨設c(u1,v1) = 1,c(u2,v1) = 2,c(u3,v1) = 3。為了滿足點(u1,v1)和(u2,v1)的多彩染色的條件，只能c(u1,v2) = 4,c(u2,v2) = 5，那么c(u3,v2)∈{1,2,3,4,5}，這與(5,3)-染色的條件相矛盾，所以χ3(C3□Pn)≥6，故m=3 時，χ3(C3□Pn)=6。

情形2.2m=6 且n=2k(k ≥1)，給出一個(6,3)-染色

矩陣A從第3 列開始循環(huán)

因為對于任意一條邊uivj ∈E(C6□Pn)，我們有c(ui)?=c(vj)，所以按照A6×n的染色c是一個(6,1)-染色。下面證明c是一個(6,3)-染色：

i) 任選一個點(ui,vk)∈V(C6□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC6□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NC6□Pn(ui,vk))|=3；

故按照A6×n這樣染色，是一個(6,3)-染色，所以χ3(C6□Pn)≤6。

接下來，用反證法證明χ3(C6□Pn)≥6。假設χ3(C6□Pn)≤5，對于第n-1 列和第n列來說，我們先對第n-1 列點進行染色，進行如下討論：

i) 如果第n-1 列按123123 的順序來染，那么第n列只能染454545，第n列的點不符合多彩染色的條件，故矛盾；

ii) 如果第n-1 列按123423 的順序來染，那么第二列只能染454，第2 列染5 的點不符合多彩染色的條件，故矛盾；

iii) 如果第n- 1 列按123453 的順序來染，無論怎樣進行染色，第2 列都會出現(xiàn)aba(a,b ∈{1,2,3,4,5})的片段，不符合多彩染色的條件，故矛盾；因此c(u3,v2)不滿足(5,3)-染色的條件，故χ3(C6□Pn)≥6。

綜上，得m=6 且n=2k(k ≥1)時，χ3(C6□Pn)=6。

情形2.3 當m=7,n ?=3k+1(k ≥1)時，給出一個(6,3)-染色

矩陣A從第3 列開始循環(huán)

因為對于任意一條邊uivj ∈E(C7□Pn)，我們有c(ui)?=c(vj)，所以按照A7×n的染色c是一個(6,1)-染色。下面證明c是一個(6,3)-染色：

i) 任選一個點(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC7□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NC7□Pn(ui,vk))|=3；

故按照A7×n這樣染色，是一個(6,3)-染色，所以χ3(C7□Pn)≤6。

接下來，用反證法證明χ3(C7□Pn)≥6。假設χ3(C7□Pn)≤5，對于任意兩列來說，如果依次設c(u1,vk) = 1,c(u2,vk) = 2,c(u7,vk) = 3,c(u1,vk+1) = 4，按照這種方式染色，第k列按最小染色數(shù)染色的染色方式為αTk= (1,2,4,3,1,2,3)。由多彩染色定義可知，第k+1 列染色情況為

由多彩染色的定義可知，c(u7,vk+1)=5,c(u7,vk+1)滿足染色。第k+2 列染色情況為

且可知

因此c(u7,vk+2)不滿足(5,3)-染色的條件，χ3(C7□Pn)≥6，故m= 7,n ?= 3k+1(k ≥1)時，χ3(C7□Pn)=6。

情形2.4 當m=11 且n ?=3k+1(k ≥1)時，給出一個(6,3)-染色

矩陣A從第3 列開始循環(huán)

因為對于任意一條邊uivj ∈E(C11□Pn)(n ?=3k+1,k ≥1)，我們有c(ui)?=c(vj)，所以按照A11×n的染色c是一個(6,1)-染色。下面證明c是一個(6,3)-染色：

i) 任選一個點(ui,vk)∈V(C11□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC11□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NC11□Pn(ui,vk))|=3；

故按照A11×n這樣染色，是一個(6,3)-染色，所以χ3(C11□Pn)≤6。

接下來，用反證法證明χ3(C11□Pn)≥6。假設χ3(C11□Pn)≤5，對于任意兩列來說，如果依次設c(u1,vk) = 1,c(u2,vk) = 2,c(u11,vk) = 3,c(u1,vk+1) = 4，按這種方式進行染色，第k列按最小染色數(shù)染色的方式為αTk= (1,2,4,3,1,2,4,3,1,2,3)。由多彩染色的定義可知，第k+1 列的情況為

因此c(u11,vk+2)不滿足(5,3)-染色的條件，故m=11 且n ?=3k+1(k ≥1)時，χ3(C11□Pn)=6。

情形3 i) 4 ?m且m ?={3,6,7,11}。

ii)m=6 且n=2k(k ≥1)。

iii)m ∈{7,11}且n=3k+1(k ≥1)。

我們分以下三種情況討論。

情形3.1m ≡1(mod 4)給出一個(5,3)-染色因為對于任意一條邊uivj ∈E(Cm□Pn)，我們有c(ui)?=c(vj)，所以按照Am×n的染色c是一個(5,1)-染色。下面證明c是一個(5,3)-染色：

i) 任選一個點(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk) = 4，我們有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n這樣染色，是一個(5,3)-染色，所以χ3(Cm□Pn)≤5。

接下來，用反證法證明χ3(Cm□Pn)≥5。假設χ3(Cm□Pn)≤4，對于第1 列和第2 列來說，假設依次設c(u1,v1) = 1,c(u2,v1) = 2,c(u3,v1) = 3,c(u4,v1) =4,c(u5,v1) = 3，按這種方式染色，由多彩染色定義可知，第2 列染色肯定會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾。因此c不滿足(4,3)-染色的條件，故m ≡1(mod 4)時，χ3(Cm□Pn)=5。

情形3.2m ≡2(mod 4)，可分為以下兩種情形。

情形3.2.1m ≡2(mod 4)且m ?=6 時，給出一個(5,3)-染色

因為對于任意一條邊uivj ∈E(Cm□Pn)，我們有c(ui)?=c(vj)，所以按照Am×n的染色c是一個(6,1)-染色。下面證明c是一個(6,3)-染色：

i) 任選一個點(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk) = 4，我們有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n這樣染色，是一個(6,3)-染色，所以χ3(Cm□Pn)≤6。

接下來，用反證法證明χ3(Cm□Pn)≥5。假設χ3(Cm□Pn)≤4，取第1 列和第2 列兩列，對于第1 列：

i) 如果我們按照121234···1234 的序列來染色，為了滿足第1 列的點的多彩染色的條件，那么在第2 列肯定會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾；

ii) 如果我們按照12341234··· 的序列來染色，要么在第1 列出現(xiàn)aba(ab ∈{1234})的染色片段，要么在第2 列出現(xiàn)44···44 的染色片段，這與多彩染色的條件矛盾；故m ≡2(mod 4)且m ?=6 時，χ3(Cn□Pm)=5。

情形3.2.2 當m=6 且n=2k+1(k ≥1)時，取

矩陣A6×n={α1,α2,···,αn}滿足

因為對于任意一條邊uivj ∈E(C6□Pn)，我們有c(ui)?=c(vj)，所以按照A6×n的染色c是一個(5,1)-染色。下面證明c是一個(5,3)-染色：

i) 任選一個點(ui,vk)∈V(C6□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC6□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk) = 4，我們有|c(NC6□Pn(ui,vk))|=3；

故按照A6×n這樣染色，是一個(5,3)-染色，所以χ3(C6□Pn)≤5。

接下來，用反證法證明χ3(C6□Pn)≥5。假設χ3(C6□Pn)≤4，取第1 列和第2 列兩列，我們進行如下討論：

i) 如果第1 列，我們按照123123 來染色，為了滿足第1 列的點的多彩染色的條件，那么在第2 列肯定會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾；

ii) 如果第1 列，我們按照123423 來染色，為了滿足第1 列的點的多彩染色的條件，那么在第2 列也會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾；故m=6 且n=2k+1(k ≥1)時，χ3(C6□Pn)=5。

情形3.3m ≡3(mod 4)且m/∈{3,7,11}或m={7,11}且n= 3k+1(k ≥1)。給出一個(5,3)-染色。

情形3.3.1 當m ≡3(mod 4)且m/∈{3,7,11}時，令

因為對于任意一條邊uivj ∈E(Cm□Pn)，我們有c(ui)?=c(vj)，所以按照Am×n的染色c是一個(5,1)-染色。下面證明c是一個(5,3)-染色：

i) 任選一個點(ui,vk)∈V(Cm□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NCm□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk) = 4，我們有|c(NCm□Pn(ui,vk))|=3；

故按照Am×n這樣染色，是一個(5,3)-染色，所以χ3(Cm□Pn)≤5。

接下來，用反證法證明χ3(Cm□Pn)≥5。假設χ3(Cm□Pn)≤4，對于第1 列和第2 列來說，如果第1 列按照序列1231234···1234 來進行染色，那么在第2 列上肯定會出現(xiàn)44 的染色片段。這與正常染色的條件相矛盾，因此c不滿足(4,3)-染色的條件，χ3(Cm□Pn)≥5，故m ≡3(mod 4)且m/∈{7,11}時，χ3(Cm□Pn)=5。

情形3.3.2 當m=7,n=3k+1(k ≥1)時，令

矩陣A7×n={α1,α2,···,αn}滿足

因為對于任意一條邊uivj ∈E(C7□Pn)，我們有c(ui)?=c(vj)，所以按照A7×n的染色c是一個(5,1)-染色。下面證明c是一個(5,3)-染色：

i) 任選一個點(ui,vk)∈V(C7□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC7□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk) = 4，我們有|c(NC7□Pn(ui,vk))|=3；

故按照A7×n這樣染色，是一個(5,3)-染色，所以χ3(C7□Pn)≤5。

接下來，用反證法證明χ3(C7□Pm)≥5。假設χ3(C7□Pm)≤4，取第1 列和第2 列兩列，我們進行如下討論：如果第1 列按照1234123 來染色，為了滿足第1 列的點的多彩染色的條件，那么在第2 列肯定會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾，故m= 7,n= 3k+1(k ≥1)時，χ3(C7□Pm)≥5。因此，當m= 7,n= 3k+1(k ≥1)時，χ3(C7□Pm)=5。

情形3.3.3 當m=11,n=3k+1(k ≥1)時，令因為對于任意一條邊uivj ∈E(C11□Pn)，我們有c(ui)?=c(vj)，所以按照A11×n的染色c是一個(5,1)-染色。下面證明c是一個(5,3)-染色：

i) 任選一個點(ui,vk)∈V(C11□Pn)(i ∈{1,n})，并且d(ui,vk) = 3，由染色c可知|c(NC11□Pn(ui,vk))|=3；

ii) 任選一個點(ui,vk)(i ?={1,n})，并且d(ui,vk)=4，我們有|c(NC11□Pn(ui,vk))|=3；

故按照A11×n這樣染色，是一個(5,3)-染色，所以χ3(C11□Pn)≤5。

接下來，用反證法證明χ3(C11□Pm)≥5。假設χ3(C11□Pm)≤4，取第1 列和第2 列兩列，我們進行如下討論：如果第1 列，我們按照12341234123 來染色，為了滿足第1 列的點的多彩染色的條件，那么在第2 列肯定會出現(xiàn)44 的染色片段，這與正常染色的條件矛盾，故m=11,n=3k+1(k ≥1)時，χ(C11□Pm)≥5。

綜上，4 ?m且m ?={3,6,7,11}；m= 6 且n= 2k(k ≥1)；m ∈{7,11}且n=3k+1(k ≥1)滿足χ3(Cm□Pn)=5。

2 結(jié)論

已有文獻中證明了圈與路的笛卡爾乘積圖Cm□Pn的2-多彩染色數(shù)，我們研究了圈與路的笛卡爾乘積圖Cm□Pn的r-多彩染色數(shù)(r ∈{3,4})，本文只給出了圈與路的笛卡爾乘積圖Cm□Pn的3-多彩染色數(shù)的證明。對于r= 4 的情況，其證明方法與r= 3 時的證明方法完全相同，證明過程過于繁瑣，本文沒有一一列出。

在以后的工作中，我們可以研究任意兩個圖做笛卡爾乘積圖的正常染色數(shù)，進而研究其多彩染色數(shù)。本文的研究對于研究電力網(wǎng)絡的最優(yōu)重新配置中多代理系統(tǒng)的通訊問題具有一定的指導意義。