楊 環(huán)，田雙亮

(西北民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，甘肅 蘭州 730030)

0 引言

設(shè)G是有限簡單圖，分別用V(G)和E(G)表示G的頂點(diǎn)集和邊集，分別用Δ(G)和δ(G)表示G的最大度和最小度，分別用d(v)和d(u，v)表示頂點(diǎn)v的度和頂點(diǎn)u，v的距離， 并用Ev表示頂點(diǎn)v的所有關(guān)聯(lián)邊構(gòu)成的集合， 記(x)k=xmodk，其中x為整數(shù)，k為正整數(shù).

設(shè)σ是G的k-正常邊染色，顏色集合為[k]={0，1，2，…，k-1}.對(duì)每一頂點(diǎn)u∈V(G)，記σ＇(u)=(∑uυ∈Ευσ(uv))k. 若對(duì)G的任意相鄰頂點(diǎn)u與v，有σ＇(u) ≠σ＇(v)，則稱σ是G的k-孿生邊染色，最小的k值為G的孿生邊色數(shù)，記為χ＇t(G)，其中σ＇稱為由σ誘導(dǎo)的點(diǎn)染色. 孿生邊染色是Andrews等人在文獻(xiàn)[1]中提出的特殊邊染色概念，并在此基礎(chǔ)上，得到了路、圈、完全圖以及完全二部圖等的孿生邊色數(shù).

類似地，若G的d-距離邊染色σ誘導(dǎo)的點(diǎn)染色σ＇是G的d-距離點(diǎn)染色，則稱σ為G的孿生d-距離邊染色，最少的顏色數(shù)稱為G的孿生d-距離邊色數(shù)，記為χ＇d，t(G). 顯然，G的孿生1-距離邊染色為G的孿生邊染色，所以χ＇1，t(G)=χ＇t(G). 因圖的2-距離邊染色也稱為強(qiáng)邊染色，所以孿生2-距離邊染色也稱為孿生強(qiáng)邊染色，且孿生強(qiáng)邊色數(shù)也記為χ＇s，t(G).

由孿生d-距離邊染色概念，顯然有以下引理.

引理1 若G是階至少為3且存在相鄰最大度點(diǎn)的簡單圖，對(duì)任意正整數(shù)d1與d2， 若d1≤d2，則

Δ(G)+1≤χ＇d1，t(G)≤χ＇d2，t(G).

引理2 若G是階至少為3的簡單圖，且G的連通分支為G1，G2，…，Gω. 對(duì)任意正整數(shù)d，有

χ＇d，t(G)=max{χ＇d，t(Gi)|i=1，2，…，ω}.

與孿生邊染色密切相關(guān)的染色概念是鄰點(diǎn)可區(qū)別邊染色，其中圖G的鄰點(diǎn)可區(qū)別邊染色[2]是指G的任意相鄰頂點(diǎn)具有不同色集的正常邊染色，所用顏色數(shù)最少的值稱為鄰點(diǎn)可區(qū)別邊色數(shù)，記為χ＇a(G).

由鄰點(diǎn)可區(qū)別邊染色與孿生邊染色概念可知，圖G的任一孿生k-邊染色一定是G的一個(gè)k-鄰點(diǎn)可區(qū)別邊染色，但反之不一定成立，如3-階路的任一2-鄰點(diǎn)可區(qū)別邊染色均不是它的孿生2-邊染色. 因此，對(duì)階至少為3的簡單連通圖G，有χ＇a(G)≤χ＇t(G).

本文主要研究簡單圖G的孿生強(qiáng)邊染色， 文中未說明的符號(hào)和術(shù)語參見文獻(xiàn)[9-10].

1 主要結(jié)果及證明

設(shè)G是最大度為2的n階簡單圖， 其中n≠3， 則G的連通分支是圈或路. 若G是連通的， 則G是圈或階至少為3的路. 關(guān)于圈和路的孿生強(qiáng)邊染色， 有以下定理：

定理1.1 設(shè)G是最大度為2的n階簡單圖，其中n≥3. 若(n)3=0，則χ＇s，t(G)=3.

證明由已知，設(shè)G=v0v1…vn-1或G=v0v1…vn-1vo，其中n≠3. 由引理1可知，χ＇s，t(G)≥3. 現(xiàn)在證明χ＇s，t(G)≤3. 設(shè)顏色集合為{0，1，2}. 令

σ(vivi+1)=(i+1)3

(1)

其中，當(dāng)G為路時(shí)，i=0，1，…，n-2；當(dāng)G為圈時(shí)，i=0，1，…，n-1，且vi+1的下標(biāo)取模n.

現(xiàn)在， 需驗(yàn)證σ是G的強(qiáng)邊染色，且σ誘導(dǎo)的點(diǎn)染色σ＇為G是2-距離點(diǎn)染色.

首先， 驗(yàn)證σ是G的強(qiáng)邊染色. 任取G的距離不超過2的3條邊e，e＇與e″，不妨假設(shè)e=vivi+1，e＇=vi+1vi+2與e″=vi+2vi+3. 由式(1)可知，

σ(e)=(i+1)3，σ(e＇)=(i+2)3，σ(e″)=(i)3.

顯然，σ(e)≠σ(e＇)，σ(e)≠σ(e″)，σ(e＇)≠σ(e″)，否則可導(dǎo)出矛盾(1)3=(2)3，或(1)3=(0)3，或(2)3=(0)3. 因此，σ是G的強(qiáng)邊染色.

其次， 驗(yàn)證由σ誘導(dǎo)的點(diǎn)染色σ＇是G的2-距離染色. 由σ及σ＇的定義知，對(duì)任意vP∈V(G)，若d(vp)=1，則p=0或p=1，此時(shí)有

σ＇(v0)=1，σ＇(vn-1)=2.

(2)

若d(vP)=2， 則有

σ＇(vp)=((p)3+(p+1)3)3.

(3)

其中vp-1與vp+1的下標(biāo)取模n，下文相同.

任取G中距離不超過2的三個(gè)頂點(diǎn)x，y與z，不妨假設(shè)x=vi，y=vi+1，z=vi+2. 由式(2)與式(3)可知，對(duì)i=0，1，…，n-1，有

σ＇(v0)=1或σ＇(vi)=((i)3+(i+1)3)3，

σ＇(vi+1)=((i+1)3+(i+2)3)3，

σ＇(vi+2)=((i+2)3+(i)3)3或σ＇(vn-1)=2.

若σ＇(vi)=σ＇(vi+1)，或σ＇(vi)=σ＇(vi+2)，或σ＇(vi+1)=σ＇(vi+2)，則可導(dǎo)出矛盾1=0，或(i)3=(i+2)3，或(i+1)3=(i+2)3，或(i+1)3=(i)3.所以σ＇(vi)≠σ＇(vi+1)，σ＇(vi)≠σ＇(vi+2)，σ＇(vi+1)≠σ＇(vi+2). 因此，σ＇是G的2-距離染色.

綜上所述，σ是G的孿生強(qiáng)邊染色. 因此，χ＇s，t(G)=3.

定理1.2 設(shè)G是最大度為2的n階簡單連通圖，若(n)3=1，或(n)3=2且δ(G)=1，則χ＇s，t(G)=4.

證明由定理1.1可知，χ＇s，t(G)=3.以下用反證法證明χ＇s，t(G)≥4. 設(shè)G=v0v1…vn-1或G=v0v1…vn-1v0，且顏色集合為{0，1，2}.令σ(v0v1)=a，σ(v1v2)=b，σ(v2v3)=c，其中{a，b，c}={0，1，2}. 當(dāng)G=v0v1…vn-1v0時(shí)，因(n)3=1，所以σ(vn-1v0)=b，由σ的定義可知，σ(v1v2)=σ(vn-1v0)，因此，σ不是G的孿生強(qiáng)邊染色.

當(dāng)G=v0v1…vn-1時(shí)，由σ及其誘導(dǎo)的2-距離染色σ＇的定義可知，

σ＇(v0)=a，σ＇(v1)=(a+b)3，σ＇(v2)=(b+c)3.

當(dāng)(n)3=1，則有(n-4)3=0，(n-3)3=1，(n-2)3=2.所以，σ(vn-4vn-3)=a，σ(vn-3vn-2)=b，σ(vn-2vn-1)=c. 因此，σ＇(vn-3)=(a+b)3，σ＇(vn-2)=(b+c)3，σ＇(vn-1)=c.

由σ及σ＇的定義可知，b≠0. 因此要么a=0，要么c=0. 若a=0，則(b+c)3=0. 所以，σ＇(v0)=σ＇(v2)=0，這與σ＇是G的2-距離染色矛盾. 類似地，若c=0，則(a+b)3=0. 所以，σ＇(vn-1)=σ＇(vn-3)=0，這與σ＇是G的2-距離染色矛盾.

當(dāng)(n)3=2時(shí)，則(n-4)3=1，(n-3)3=2，(n-2)3=0. 所以σ(vn-4vn-3)=b，σ(vn-3vn-2)=c，σ(vn-2vn-1)=a. 因此，σ＇(vn-3)=(b+c)3，σ＇(vn-2)=(c+a)3，σ＇(vn-1)=a. 由σ及σ＇的定義可知，b≠0且c≠0. 否則，σ＇(v0)=σ＇(v1)，σ＇(vn-1)=σ＇(vn-2). 因此a=0，進(jìn)而(b+c)3=0. 故有σ＇(v0)=σ＇(v2)，σ＇(vn-1)=σ＇(vn-3)，這與σ＇的定義矛盾.

由以上分析知，χ＇s，t(G)>3. 設(shè)顏色集合為{0，1，2，3}，驗(yàn)證χ＇s，t(G)≤4. 證明與定理1.1類似.

綜上所述，σ是G的孿生強(qiáng)邊染色，因此，χ＇s，t(G)=4. 定理結(jié)論成立.

定理1.3 設(shè)G是最大度為2的n階簡單圖，其中n≥3. 若(n)3=2且δ(G)=2，則χ＇s，t(G)=5.

證明用反證法證明χ＇s，t(G)>4. 設(shè)G=v0v1…vn-1v0，且σ是G的孿生強(qiáng)邊染色，顏色集合為{0，1，2，3}. 不妨設(shè)

σ(v0v1)=0，σ(v1v2)=a，σ(v2v3)=b，σ(v3v4)=c

其中{a，b，c}={1，2，3}. 因(n)3=2，所以σ(vn-4vn-3)=0，σ(vn-3vn-2)=a，σ(vn-2vn-1)=b，σ(vn-1v0)=c.

首先，驗(yàn)證σ是G的強(qiáng)邊染色. 因{a，b，c}={1，2，3}且(n)3=2，所以，σ是G的強(qiáng)邊染色.

其次，驗(yàn)證由σ誘導(dǎo)的點(diǎn)染色σ＇是2-距離染色. 由σ及其誘導(dǎo)的2-距離染色σ＇的定義知，對(duì)每一點(diǎn)vl∈V(G)，當(dāng)l=0，1，…，n-1時(shí)，若d(vl)=2， 則有

σ＇(v0)=(σ(v0v1)+σ(vn-1v0))4，

σ＇(vn-1)=(σ(vn-2vn-1)+σ(vn-1v0))4，

σ＇(vl)=(σ(vl-1vl)+σ(vlvl+1))4.

其中vl-1與vl+1的下標(biāo)取模n，下文相同.

任取G中距離不超過2的三個(gè)頂點(diǎn)x，y與z，不妨假設(shè)x=vi，y=vi+1，z=vi+2.由σ及σ＇的定義可知，

σ＇(v0)=c，σ＇(v1)=a，σ＇(v2)=(a+b)4，σ＇(v3)=(b+c)4，

(4)

σ＇(vn-3)=a，σ＇(vn-2)=(a+b)4，σ＇(vn-1)=(b+c)4.

(5)

因{a，b，c}={1，2，3}，則a，b，c的取值有6種情形：①a=1，b=2，c=3； ②a=1，b=3，c=2；③a=2，b=1，c=3; ④a=2，b=3，c=1;⑤a=3，b=1，c=2;⑥a=3，b=2，c=2. 僅討論a=1的兩種情形，其他可類似討論.

情形1b=2，c=3.

由式(4)～式(5)可知，σ＇(v0)=3，σ＇，(v1)=1，σ＇(v2)=3，σ＇(v3)=1，σ＇(vn-3)=1，σ＇(vn-2)=3，σ＇(vn-1)=1. 當(dāng)d(vivj)=1時(shí)，顯然，σ＇(v0)≠σ＇(v1)，σ＇(v0)≠σ＇(vn-1)，σ＇(v1)≠σ＇(v2)，σ＇(v2)≠σ＇(v3)，σ＇(vn-3)≠σ＇(vn-2)，σ＇(vn-2)≠σ＇(vn-1). 所以，當(dāng)d(vi，vj)=1時(shí)，σ＇(vi)≠σ＇(vj). 當(dāng)d(vivj)=2時(shí)，顯然，σ＇(v0)=σ＇(v2)，σ＇(v0)=σ＇(vn-2)，σ＇(v1)=σ＇(v3)，σ＇(v1)=σ＇(vn-1). 所以，當(dāng)d(vi，vj)=2時(shí)，σ＇(vi)=σ＇(vj). 因此，σ＇不是G的2-距離染色.

情形2b=3，c=2.

由式(4)式(5)可知，σ＇(v0)=2，σ＇(v1)=1，σ＇(v2)=0，σ＇(v3)=1，σ＇(vn-3)=1，σ＇(vn-2)=0，σ＇(vn-1)=1.當(dāng)d(vivj)=1時(shí)，顯然，σ＇(v0)≠σ＇(v1)，σ＇(v0)≠σ＇(vn-1)，σ＇(v1)≠σ＇(v2)，σ＇(v2)≠σ＇(v3)，σ＇(vn-3)≠σ＇(vn-2)，σ＇(vn-2)≠σ＇(vn-1). 所以，當(dāng)d(vi，vj)=1時(shí)，σ＇(vi)≠σ＇(vj). 當(dāng)d(vivj)=2時(shí)，顯然，σ＇(v1)=σ＇(v3)，σ＇(vn-3)=σ＇(vn-1). 所以，當(dāng)d(vi，vj)=2時(shí)，σ＇(vi)=σ＇(vj). 因此，σ＇不是G的2-距離染色.

由以上分析可知，σ不是G的孿生強(qiáng)邊染色. 因此，χ＇s，t(Pn)>4.設(shè)顏色集合為{0，1，2，3，4}，驗(yàn)證χ＇s，t(G)≤5. 證明與定理1.1類似.

綜上所述，σ是G的孿生強(qiáng)邊染色，因此，χ＇s，t(G)=5.

2 結(jié)論

根據(jù)定理1.1至定理1.3的結(jié)果，可得到以下結(jié)論：當(dāng)G是最大度為2的不含孤立邊和孤立點(diǎn)的n階路或圈時(shí)，若(n)3=0，則G的孿生強(qiáng)邊染色數(shù)為3；若(n)3=1，或(n)3=2且δ(G)=1，則G的孿生強(qiáng)邊染色數(shù)為4；若(n)3=2且δ(G)=2，則G的孿生強(qiáng)邊染色數(shù)為5.