楊 環(huán)

(?？诮?jīng)濟學(xué)院 聚星數(shù)字經(jīng)濟學(xué)院，海南 海口 570100)

0 引言

在孿生邊染色概念基礎(chǔ)上，可以定義以下更一般的帶有限制條件的邊染色概念.

在定義1中，孿生1-距離邊染色也叫孿生邊染色.因2-距離邊染色也稱為強邊染色[4]，所以孿生2距離-邊染色也稱為孿生強邊染色[5].

引理1 設(shè)G是階至少為3的簡單圖,且G的連通分支為G1,G2,…，Gω，有

本文主要研究無限路的孿生強邊染色，以及無限路的笛卡爾積、直積的孿生邊染色，文中未說明的符號及術(shù)語可參見文獻[6]與[7]．

1 主要結(jié)果

設(shè)P∞為無限路，且V(P∞)=Z(Z為整數(shù)集),其中V(P∞)中任意不同頂點i與j相鄰當(dāng)且僅當(dāng)

|i-j|=1．設(shè)CP(d)與DP(d)分別為d個無限路的笛卡爾積與直積，并分別記為CP(d)=P∞□P∞□…□P∞與DP(d)=P∞∧P∞∧…∧P∞，且它們的頂點集為V(CP(d))=V(DP(d))={(x1,x2,…，xd)|xi∈Z,i=1,2,…,d}，其中d≥2.

關(guān)于無限路的孿生強邊染色，有以下定理1及證明.

首先,驗證σ是P∞的2-距離邊染色.顯然,P∞中彼此距離不超過2的邊最多有3條.任取P∞的距離不超過2的3條邊e=vivi+1，e＇=vi+1vi+2與e″=vi+2vi+3.由σ的定義可知，σ(e)=(i)3，σ(e')=(i+1)3，σ(e″)=(i+2)3.顯然e，e＇，e″具有不同的顏色，所以σ是P∞的2-距離邊染色.

其次,驗證由σ誘導(dǎo)的點染色σ＇是P∞的2-距離染色.

任取P∞中距離不超過2的三個頂點vi，vi+1，vi+2.由σ及σ＇的定義可知，σ'(vi)=(2i+2)3，σ'(vi+1)=(2i+1)3，σ'(vi+2)=(2i)3.顯然，σ'(vi)≠σ'(vi+1)，σ'(vi)≠σ'(vi+2)，σ'(vi+1)≠σ'(vi+2).否則，可推出矛盾：0=1，或1=2，或0=2.因此，P∞中距離不超過2的點在σ＇下染不同的顏色，即σ＇是P∞的2-距離染色.

由以上分析可知，σ是P∞的一個3-孿生強邊染色.

關(guān)于Cp(d)的孿生邊色數(shù)，有以下結(jié)果：

設(shè)ei=(x1,x2,…，xi，…，xd)(x1,x2,…，xi+1，…，xd)，對每一i=1,2,…d，令

顯然，σ所用顏色數(shù)為k.下面證明σ是G的正常邊染色，且由σ誘導(dǎo)的點染色σ＇是G的正常點染色.

首先,證明σ是G的正常邊染色.設(shè)uv與vw為G的任意相鄰兩邊，其中

v=(x1,x2,…，xi，…，xd),u=(x1,x2,…，xi+θ1，…，xd),u=(x1,x2,…，xi+θ2，…，xd).

且θ1=±1，θ2=±1.由σ的定義知，

其次，驗證由σ誘導(dǎo)的點染色σ＇是G的正常點染色.

對G中每一頂點v=(x1,x2,…，xd)，其鄰邊有2d條.由σ與σ＇的定義知，

顯然，σ'(v)≠σ'(u)，否則，(2dθ)k=0，這與θ=±1，k=2d+1矛盾.因此，σ＇是G的正常點染色.

由以上分析可知，σ是G的一個(2d+1)-孿生邊染色.

為研究DP(d)的孿生邊染色，首先給出以下兩個引理：

引理2 設(shè)G是局部有限無限圖.若G存在k-邊染色(或k-孿生邊染色)，則G∧P2存在k-邊染色(或k-孿生邊染色).

證明設(shè)P2的頂點集為{0,1}，并設(shè)顏色集合為{0,1,…，k-1}.

其中E*=E(G∧P2),E=E(G).

任取G∧P2的兩個相鄰頂點(x,0)與(y,1)，則

引理3 對任意正整數(shù)d，有χ＇(Dp(d))=2d，其中χ＇(Dp(d))表示Dp(d)的邊色數(shù).

證明用數(shù)學(xué)歸納法證明.當(dāng)d=1時，Dp(1)=P∞，顯然，χ＇(Dp(d))=2d.假設(shè)當(dāng)2≤d≤k時定理結(jié)論成立.現(xiàn)在證明χ＇(Dp(d+1))=2d+1.由圖直積的定義知，Δ(DP(d+1))=2d+1.所以χ＇(Dp(d+1))≥2d+1.為證明χ＇(Dp(d+1))≤2d+1，下面構(gòu)造DP(d+1)的一個(2d+1)-邊染色.

由歸納假設(shè)，可設(shè)σ為DP(d)的一個2d-邊染色,其中顏色集合為[2d]0.現(xiàn)在，對DP(d+1)的每個子圖Hi進行邊染色.具體地，若DP(d)中頂點x=(x1,x2,…，xd)與y=(y1,y2,…，yd)相鄰，則令

關(guān)于DP(d)的孿生邊染色,有以下定理3.

證明用數(shù)學(xué)歸納法證明.當(dāng)d=2時，顯然，DP(2)可表示為兩個不相交的CP(d)之并.

首先，由歸納假設(shè)，DP(d)存在(2d+1)-孿生邊染色，根據(jù)引理2，DP(d)∧P2存在一個(2d+1)-孿生邊染色，記為σ0，所用顏色集為[2d+1]0.由引理3，DP(d)存在(2d)-邊染色，由引理2，DP(d)∧P2存在一個(2d)-邊染色，記為σ1，所用顏色集為[2d+1+1]0-[2d+1]0.