杨 环，田双亮

(西北民族大学 数学与计算机科学学院，甘肃 兰州 730030)

0 引言

设G是有限简单图，分别用V(G)和E(G)表示G的顶点集和边集，分别用Δ(G)和δ(G)表示G的最大度和最小度，分别用d(v)和d(u，v)表示顶点v的度和顶点u，v的距离， 并用Ev表示顶点v的所有关联边构成的集合， 记(x)k=xmodk，其中x为整数，k为正整数.

设σ是G的k-正常边染色，颜色集合为[k]={0，1，2，…，k-1}.对每一顶点u∈V(G)，记σ＇(u)=(∑uυ∈Ευσ(uv))k. 若对G的任意相邻顶点u与v，有σ＇(u) ≠σ＇(v)，则称σ是G的k-孪生边染色，最小的k值为G的孪生边色数，记为χ＇t(G)，其中σ＇称为由σ诱导的点染色. 孪生边染色是Andrews等人在文献[1]中提出的特殊边染色概念，并在此基础上，得到了路、圈、完全图以及完全二部图等的孪生边色数.

类似地，若G的d-距离边染色σ诱导的点染色σ＇是G的d-距离点染色，则称σ为G的孪生d-距离边染色，最少的颜色数称为G的孪生d-距离边色数，记为χ＇d，t(G). 显然，G的孪生1-距离边染色为G的孪生边染色，所以χ＇1，t(G)=χ＇t(G). 因图的2-距离边染色也称为强边染色，所以孪生2-距离边染色也称为孪生强边染色，且孪生强边色数也记为χ＇s，t(G).

由孪生d-距离边染色概念，显然有以下引理.

引理1 若G是阶至少为3且存在相邻最大度点的简单图，对任意正整数d1与d2， 若d1≤d2，则

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

引理2 若G是阶至少为3的简单图，且G的连通分支为G1，G2，…，Gω. 对任意正整数d，有

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

与孪生边染色密切相关的染色概念是邻点可区别边染色，其中图G的邻点可区别边染色[2]是指G的任意相邻顶点具有不同色集的正常边染色，所用颜色数最少的值称为邻点可区别边色数，记为χ＇a(G).

由邻点可区别边染色与孪生边染色概念可知，图G的任一孪生k-边染色一定是G的一个k-邻点可区别边染色，但反之不一定成立，如3-阶路的任一2-邻点可区别边染色均不是它的孪生2-边染色. 因此，对阶至少为3的简单连通图G，有χ＇a(G)≤χ＇t(G).

本文主要研究简单图G的孪生强边染色， 文中未说明的符号和术语参见文献[9-10].

1 主要结果及证明

设G是最大度为2的n阶简单图， 其中n≠3， 则G的连通分支是圈或路. 若G是连通的， 则G是圈或阶至少为3的路. 关于圈和路的孪生强边染色， 有以下定理：

定理1.1 设G是最大度为2的n阶简单图，其中n≥3. 若(n)3=0，则χ＇s，t(G)=3.

证明由已知，设G=v0v1…vn-1或G=v0v1…vn-1vo，其中n≠3. 由引理1可知，χ＇s，t(G)≥3. 现在证明χ＇s，t(G)≤3. 设颜色集合为{0，1，2}. 令

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

(1)

其中，当G为路时，i=0，1，…，n-2；当G为圈时，i=0，1，…，n-1，且vi+1的下标取模n.

现在， 需验证σ是G的强边染色，且σ诱导的点染色σ＇为G是2-距离点染色.

首先， 验证σ是G的强边染色. 任取G的距离不超过2的3条边e，e＇与e″，不妨假设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″)，否则可导出矛盾(1)3=(2)3，或(1)3=(0)3，或(2)3=(0)3. 因此，σ是G的强边染色.

其次， 验证由σ诱导的点染色σ＇是G的2-距离染色. 由σ及σ＇的定义知，对任意vP∈V(G)，若d(vp)=1，则p=0或p=1，此时有

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

(2)

若d(vP)=2， 则有

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

(3)

其中vp-1与vp+1的下标取模n，下文相同.

任取G中距离不超过2的三个顶点x，y与z，不妨假设x=vi，y=vi+1，z=vi+2. 由式(2)与式(3)可知，对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)，则可导出矛盾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的孪生强边染色. 因此，χ＇s，t(G)=3.

定理1.2 设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. 设G=v0v1…vn-1或G=v0v1…vn-1v0，且颜色集合为{0，1，2}.令σ(v0v1)=a，σ(v1v2)=b，σ(v2v3)=c，其中{a，b，c}={0，1，2}. 当G=v0v1…vn-1v0时，因(n)3=1，所以σ(vn-1v0)=b，由σ的定义可知，σ(v1v2)=σ(vn-1v0)，因此，σ不是G的孪生强边染色.

当G=v0v1…vn-1时，由σ及其诱导的2-距离染色σ＇的定义可知，

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

当(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-距离染色矛盾.

当(n)3=2时，则(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，进而(b+c)3=0. 故有σ＇(v0)=σ＇(v2)，σ＇(vn-1)=σ＇(vn-3)，这与σ＇的定义矛盾.

由以上分析知，χ＇s，t(G)>3. 设颜色集合为{0，1，2，3}，验证χ＇s，t(G)≤4. 证明与定理1.1类似.

综上所述，σ是G的孪生强边染色，因此，χ＇s，t(G)=4. 定理结论成立.

定理1.3 设G是最大度为2的n阶简单图，其中n≥3. 若(n)3=2且δ(G)=2，则χ＇s，t(G)=5.

证明用反证法证明χ＇s，t(G)>4. 设G=v0v1…vn-1v0，且σ是G的孪生强边染色，颜色集合为{0，1，2，3}. 不妨设

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

首先，验证σ是G的强边染色. 因{a，b，c}={1，2，3}且(n)3=2，所以，σ是G的强边染色.

其次，验证由σ诱导的点染色σ＇是2-距离染色. 由σ及其诱导的2-距离染色σ＇的定义知，对每一点vl∈V(G)，当l=0，1，…，n-1时，若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的下标取模n，下文相同.

任取G中距离不超过2的三个顶点x，y与z，不妨假设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(vivj)=1时，显然，σ＇(v0)≠σ＇(v1)，σ＇(v0)≠σ＇(vn-1)，σ＇(v1)≠σ＇(v2)，σ＇(v2)≠σ＇(v3)，σ＇(vn-3)≠σ＇(vn-2)，σ＇(vn-2)≠σ＇(vn-1). 所以，当d(vi，vj)=1时，σ＇(vi)≠σ＇(vj). 当d(vivj)=2时，显然，σ＇(v0)=σ＇(v2)，σ＇(v0)=σ＇(vn-2)，σ＇(v1)=σ＇(v3)，σ＇(v1)=σ＇(vn-1). 所以，当d(vi，vj)=2时，σ＇(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(vivj)=1时，显然，σ＇(v0)≠σ＇(v1)，σ＇(v0)≠σ＇(vn-1)，σ＇(v1)≠σ＇(v2)，σ＇(v2)≠σ＇(v3)，σ＇(vn-3)≠σ＇(vn-2)，σ＇(vn-2)≠σ＇(vn-1). 所以，当d(vi，vj)=1时，σ＇(vi)≠σ＇(vj). 当d(vivj)=2时，显然，σ＇(v1)=σ＇(v3)，σ＇(vn-3)=σ＇(vn-1). 所以，当d(vi，vj)=2时，σ＇(vi)=σ＇(vj). 因此，σ＇不是G的2-距离染色.

由以上分析可知，σ不是G的孪生强边染色. 因此，χ＇s，t(Pn)>4.设颜色集合为{0，1，2，3，4}，验证χ＇s，t(G)≤5. 证明与定理1.1类似.

综上所述，σ是G的孪生强边染色，因此，χ＇s，t(G)=5.

2 结论

根据定理1.1至定理1.3的结果，可得到以下结论：当G是最大度为2的不含孤立边和孤立点的n阶路或圈时，若(n)3=0，则G的孪生强边染色数为3；若(n)3=1，或(n)3=2且δ(G)=1，则G的孪生强边染色数为4；若(n)3=2且δ(G)=2，则G的孪生强边染色数为5.