無限路及其笛卡爾積、直積的孿生α-距離邊染色

楊 環(huán)

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

0 引言

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

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

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

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

1 主要結(jié)果

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

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

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

首先,驗(yàn)證σ是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-距離邊染色.

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

任取P∞中距離不超過2的三個(gè)頂點(diǎn)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的點(diǎn)在σ＇下染不同的顏色，即σ＇是P∞的2-距離染色.

由以上分析可知，σ是P∞的一個(gè)3-孿生強(qiáng)邊染色.

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

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

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

首先,證明σ是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.由σ的定義知，

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

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

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

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

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

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

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

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

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

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

證明用數(shù)學(xué)歸納法證明.當(dāng)d=1時(shí)，Dp(1)=P∞，顯然，χ＇(Dp(d))=2d.假設(shè)當(dāng)2≤d≤k時(shí)定理結(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)的一個(gè)(2d+1)-邊染色.

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

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

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

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