路的強積的鄰點可區(qū)別邊染色

安卓莫 ,田雙亮,2,蔡 瑾

(1.西北民族大學 數學與計算機科學學院,甘肅 蘭州 730030；2.西北民族大學 動態(tài)流數據計算與應用重點實驗室,甘肅 蘭州 730030)

0 引言

本文所考慮的圖G都是有限、無向的簡單連通圖,用V(G)與E(G)分別表示G的頂點集和邊集,并用Δ(G)表示G的最大度，記(x)k=x(modk),其中x為整數,k為正整數.

由鄰點可區(qū)別邊染色概念,容易得到以下引理.

引理1.1 若階至少為3的簡單圖G中存在相鄰的最大度點,則

χ＇α(G)≥Δ(G)+1.

zhang等在文獻[1]中提出了鄰點可區(qū)別邊染色概念,并研究了一些基本簡單圖，如路、圈、完全圖、樹等的鄰點可區(qū)別邊染色,得到了相應的鄰點可區(qū)別邊色數.Balister在文獻[2]中證明了最大度為3的圖的鄰點可區(qū)別邊色數不超過5,二部圖的鄰點可區(qū)別邊色數不超過其最大度加2,并證明這些上界是可達的.Hatami在文獻[3]中證明了任意圖的鄰點可區(qū)別邊色數不超過其最大度加300.由于圖的結構運算是構造圖的重要方法和手段,因此,研究運算圖的鄰點可區(qū)別的邊染色有助于確定一般圖類的相應染色數.常見的圖結構運算有圖的字典積、圖的笛卡爾積、圖的聯，以及圖的半強積、直積等等.Tian等在文獻[4]與[5]中研究了一些特殊圖的字典積與笛卡爾積的鄰點可區(qū)別的邊染色,得到了相應的鄰點可區(qū)別邊色數.Baril、Chen等在文獻[6]與[7]中得到了一些網格圖與超立方體的鄰點可區(qū)別的邊色數.何雪等在文獻[8]中給出了一些特殊圖的倍圖(即二階路與圖的半強積)的鄰點可區(qū)別邊色數.

設Pm=v0v1…vm-1,Pn=v0v1…vn-1是兩條路,其中m,n≥2.為了方便敘述,用(x,y)表示V(Pm)×V(Pn)中的頂點(uy,ux).文中未說明的符號及術語可參考文獻[10].

1 路的強積的鄰點可區(qū)別邊染色

σ((x,y)(x,(y+1)2))=(x+2)6,x=0,1,…,n-1,y=0，1，

σ((x,y)(x+1,(y+1)2))=(x+4)6,x=0,1,…,n-2,y=0，1，

σ((x,y)(x+1,y))=(x+y)6,x=0,1,…,n-2,y=0，1.

顯然,σ所用顏色集合為C={0,1,…，5}.

首先,驗證σ是G的正常邊染色.對每一個頂點(x,y)∈V(G),當1≤x≤n-2時,頂點(x,y)的關聯邊分別為

e1=(x,y)(x+1,y),e2=(x,y)(x+1,(y+1)2),e3=(x,y)(x,(y+1)2),

e4=(x-1,(y+1)2)(x,y),e5=(x-1,y)(x,y).

當x=0時,頂點(x,y)的關聯邊分別為

e1=(x,y)(x+1,y),e2=(x,y)(x+1,(y+1)2),e3=(x,y)(x,(y+1)2).

當x=n-1時,頂點(x,y)的關聯邊分別為

e3=(x,y)(x,(y+1)2)(x,y),e4=(x-1,(y+1)2)(x,y),e5=(x-1,y)(x,y).

由σ定義可知,5條邊e1、e2、e3、e4、e5的顏色分別為

σ(e1)=(x+y)6,σ(e2)=(x+4)6,σ(e3)=(x+2)6,

σ(e4)=(x+3)6,σ(e5)=(x+y-1)6=(x+y+5)6

容易驗證,這5條邊染不同的顏色,即σ是G的一個正常邊染色,且有

C(0,y)={y,2,4},C(n-1,y)={(n+1)6,(n+2)6,(n+y+4)6},y=0,1.

(1)

(2)

其次,驗證σ是鄰點可區(qū)別的.顯然,僅需證明具有相同度的相鄰頂點有不同的色集.任取度相同的兩個相鄰頂點u=(x,y)與u=(x＇,y＇),不妨設x≤x＇.假設C(u)=C(v),則可推出矛盾.

根據路的強積的結構特征,d(u)=3或d(u)=5,且v可能是3個頂點之一：

①v1=(x+1,y);②v2=(x+1,(y+1)2);③v3=(x,(y+1)2).

若d(u)=3,則v=v3=(x,(y+1)2).此時,x=0或x=n-1.當x=0時,由式(1)可知,對每一y=0,1,有C(u)={y,2,4},C(v)={(y+1)2,2,4}.

當x=n-1時,對每一y=0,1,有

C(u)={(n+1)6,(n+2)6,(n+y+4)6},C(v)={(n+1)6,(n+2)6,(n+(y+1)2+4)6}.

由C(u)=C(v)可推出矛盾:y=(y+1)2.

又因C(u)=C(v),所以(4((y)2-(y+1)2))6=1,這是不可能的,因(y)2-(y+1)2=±1.當v=v3時,則1≤x≤n-2,由式(2)可知,

由C(u)=C(v)可推出矛盾：(y)2=(y+1)2.

由以上分析,σ是鄰點可區(qū)別的.因此,定理結論成立.

σ((x,y)(x+1,y))=(x+2y)9,x=0,1,…，n-2,y=0,1,…，m-1；

σ((x,y)(x,y+1))=(x+2y+4)9,x=0,1,…，n-1,y=0,1,…，m-2；

σ((x,y)(x+1,y+1))=(x+2y+1)9,x=0,1,…，n-2,y=0,1,…，m-2；

σ((x,y+1)(x+1,y))=(x+2y+7)9,x=0,1,…，n-2,y=0,1,…，m-2.

顯然,σ所用顏色集合為C={0,1,…，8}.

首先,驗證σ是G的正常邊染色,對每個頂點(x,y)∈V(G),頂點(x,y)的所有可能關聯邊分別為

e1=(x,y)(x+1,y),e2=(x,y)(x+1,y+1),e3=(x,y)(x,y+1),e4=(x-1,y+1)(x,y),

e5=(x-1,y)(x,y),e6=(x-1,y-1)(x,y),e7=(x,y-1)(x,y),e8=(x,y)(x+1,y-1).

由σ定義可知,邊e1,e2,…，e8所染顏色分別為

σ(e1)=(x+2y)9,σ(e2)=(x+2y+1)9,σ(e3)=(x+2y+4)9,σ(e4)=(x+2y+6)9

σ(e5)=(x+2y+8)9,σ(e6)=(x+2y+7)9,σ(e7)=(x+2y+2)9,σ(e8)=(x+2y+5)9.

容易驗證,(x,y)的不同關聯邊染不同顏色,即σ是G的一個正常邊染色,且對x=1,2,…，n-2,y=1,2,…，m-2,有

(3)

(4)

(5)

(6)

(7)

其次,驗證σ是鄰點可區(qū)別的.顯然,僅需證明具有相同度的相鄰頂點有不同的色集.任取度相同的兩個相鄰頂點u=(x,y)與v=(x＇,y＇),不妨設x＇≥x,且當x＇=x時,設y＇>y,假設C(u)=C(v),可推出矛盾.

由路的強積的結構可知,d(u)=5或d(u)=8.下面分兩種情況討論.

情況1d(u)=5.此時,u的鄰點v是以下兩種情況之一：①v=(x,y+1),其中x=0或x=n-1,y=1,2,…，m-3；②v=(x+1,y),其中y=0或y=m-1,x=1,2,…，n-3.

①v=(x,y+1).當x=0時,由式(3)可知,對y=1,2,…，m-3,頂點u與v上缺少顏色之和,分別為

②u=(x+1,y).當y=0時,由式(5)可知,對x=1,2,…，n-3,頂點u與v上缺少顏色之和,分別為

情況2d(u)=8.此時,u的鄰點v是以下四種情況之一：

①v=v1=(x+1,y)，其中x=1,2,…，n-3,y=1,2,…，m-2;

②v=v2=(x,y+1),其中x=1,2,…，n-2,y=1,2,…，m-3;

③v=v3=(x+1,y+1),其中x=1,2,…，n-3,y=1,2,…，m-3;

④v=v4=(x+1,y-1),其中x=1,2,…，n-3,y=1,2,…，m-2.

由式(7)可知,頂點u及其鄰點的缺少顏色集合分別為

顯然,對每一i=1,2,3,4,有C(u)≠C(vi),這與C(u)=C(v)矛盾.

綜合情況1與情況2，σ是鄰點可區(qū)別的.因此,定理結論成立.