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

(1.西北民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,甘肅 蘭州 730030；2.西北民族大學(xué) 動(dòng)態(tài)流數(shù)據(jù)計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,甘肅 蘭州 730030)

0 引言

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

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

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

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

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

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

1 路的強(qiáng)積的鄰點(diǎn)可區(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}.

首先,驗(yàn)證σ是G的正常邊染色.對每一個(gè)頂點(diǎn)(x,y)∈V(G),當(dāng)1≤x≤n-2時(shí),頂點(diǎn)(x,y)的關(guān)聯(lián)邊分別為

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).

當(dāng)x=0時(shí),頂點(diǎn)(x,y)的關(guān)聯(lián)邊分別為

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

當(dāng)x=n-1時(shí),頂點(diǎn)(x,y)的關(guān)聯(lián)邊分別為

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

容易驗(yàn)證,這5條邊染不同的顏色,即σ是G的一個(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)

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

根據(jù)路的強(qiáng)積的結(jié)構(gòu)特征,d(u)=3或d(u)=5,且v可能是3個(gè)頂點(diǎn)之一：

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

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

當(dāng)x=n-1時(shí),對每一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.當(dāng)v=v3時(shí),則1≤x≤n-2,由式(2)可知,

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

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

σ((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}.

首先,驗(yàn)證σ是G的正常邊染色,對每個(gè)頂點(diǎn)(x,y)∈V(G),頂點(diǎn)(x,y)的所有可能關(guān)聯(lián)邊分別為

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.

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

(3)

(4)

(5)

(6)

(7)

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

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

情況1d(u)=5.此時(shí),u的鄰點(diǎn)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).當(dāng)x=0時(shí),由式(3)可知,對y=1,2,…，m-3,頂點(diǎn)u與v上缺少顏色之和,分別為

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

情況2d(u)=8.此時(shí),u的鄰點(diǎn)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)可知,頂點(diǎn)u及其鄰點(diǎn)的缺少顏色集合分別為

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

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