三类K重Mycielski图的邻点强可区别E-全染色

李雨虹,强会英,王洪申

(1.兰州交通大学 数理学院，甘肃 兰州 730070，2.兰州理工大学 机电工程学院，甘肃 兰州 730050)

1 引言

图染色理论是图论[1]里面很重要并且应用很广泛的一门学科，它来源于1852年“四色猜想”问题的提出. 1993年，A.C.Burris和R.H.Schelp首次提出了图的点可区别正常边染色的概念；2002年，张忠辅，刘林忠等教授在点可区别正常边染色的基础上提出了图的邻强边染色[2]；2005年，张忠辅，陈祥恩等教授结合学习传播过程中的干扰和共振现象提出了图的邻点可区别全染色[3]；2007年，张忠辅，程辉等人提出了图的邻点强可区别全染色[4]，文献[5]是邻点强可区别E-全染色的一些结果.本文在文献[5]的基础上得到了路图，圈图和星图的广义Mycielski图的邻点强可区别区别E-全染色，下面给出相关的定义：

2 基本概念

定义1[4,5]设图G是阶数至少为2的连通图， 映射f:V(G)∪E(G)→{1,2,…,k},其中k为正整数，C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}如果f满足：

(1)对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

(2)对任意的uv,uw∈E(G),u≠v,f(uv)≠f(uw);

(3)对任意的uv∈E(G),u≠v,C(u)≠C(v).

则称f为图G的k-邻点强可区别全染色，简记为k-AVSDTC.又称

χast(G)=min{k|G有k-AVSDTC}

为G的邻点强可区别全色数.

定义2[5]设图G是阶数至少为2的连通图，映射f:V(G)∪E(G)→{1,2,…,k}，其中k为自然数，C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}.如果f满足：

(1)对任意的uv∈E(G),u≠v,f(u)≠f(v),f(u)≠f(uv);

(2)对任意的uv∈E(G),u≠v,C(u)≠C(v).

则称f为G的k-邻点强可区别E-全染色，简记为k-E-AVSDETC,又称

为图的邻点强可区别E-全色数.

由图的邻点强可区别全染 色和图的邻点强可区别E-全染色的概念，下面引理成立：

定义3[6]对图G(V,E),μ(G)称为G的Mycielski,V(μ(G))=V(G)∪V′∪{w},E(μ(G))=E(G)∪{uv′|u∈V(G),v′∈V′,且uv∈E(G)}∪{wv′|v′∈V′},其中w∉V(G),V′={v′|v∈V(G)}

定义4[7]设G的顶点集合为V(G)={u1i|i=1,2,…,n}的简单图，n是正整数，称Mk(G)为G的k重Mycielski图，其中k≥2,如果

V(Mk(G))={u1.1,u1.2,…,u1.n；u2.1,u2.2,…,u2.n；…；uk.1,…,uk.n}∪{w}

E(Mk(G))=E(M(G))∪{uijui+1,l|u1ju1l∈E(G),1≤j,l≤n,1≤i≤k-1,}∪{wvkj|vkj∈V(G),1≤j≤n}.

3 主要结论及其证明

定理1 设Pn是n(n≥3)阶的路，则有

2,j≡0(mod2),1≤i≤k;1≤j≤n.φ(w)=3,由图的结构知，|C(w)|≥3 ，下面分两种情形考虑：

情形1：当|C(w)|=3 时，则点uij(除了u1j)和点w在邻点强可区别E-全染色的条件下，必存在j∈{1,2,…,n}，使得C(u1j)=C(u1,j+1),与定义矛盾.

f(uij)={1,j≡1(mod2),

2,j≡0(mod2)1≤i≤k;1≤j≤n.f(w)=5.f(u1j,u1,j+1)=3,1≤j≤n-1.

边uijui+1,l的染法分以下四种情况：

当i≡0(mod4)时：

f(uijui+1,j-1)=3,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=3,1≤i≤k-1;1≤j≤n-1.

当i≡1(mod4)时：

f(uijui+1,j-1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;1≤j≤n-1.

当i≡2(mod4)时：

f(uijui+1,j-1)=4,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=4,1≤i≤k-1;1≤j≤n-1.

当i≡3(mod4)时：

f(uijui+1,j-1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡0(mod2),

1,j≡1(mod2),

1≤i≤k-1;1≤j≤n-1.

f(wvkj)={1,j≡0(mod2),

2,j≡1(mod2),1≤j≤n.

此时，各点的色集合的补集为：

当i≡0(mod4)或i≡1(mod4)时：

{5},j≡0(mod2),

1≤i≤k-1;1≤j≤n.

当i≡2(mod4)或i≡3(mod4)时：

{5},j≡0(mod2),

1≤i≤k-1;1≤j≤n.

当k≡0(mod4)时：

{4},j≡1(mod2),

1≤j≤n.

当k≡1(mod4)时：

当k≡2(mod4)时：

{4},j≡0(mod2),1≤j≤n.

当k≡3(mod4)时：

显然，对∀uv∈E(G),有C(u)≠C(v),故结论成立.

定理2 设Sn是n(n≥4)阶的星图，则有

f(uij)={1,j=1,

2,2≤j≤n,1≤i≤k.f(w)=5.f(u11u1j)=3,2≤j≤n.

边uijui+1,l的染法如下：

f(uijui+1,1)={3,i≡0(mod4)或i≡3(mod4),

4,i≡1(mod4)或i≡2(mod4),

1≤i≤k-1;2≤j≤n.

f(ui1ui+1,j)={3,i≡0(mod4)或i≡1(mod4),

4,i≡2(mod4)或i≡3(mod4),

1≤i≤k-1;2≤j≤n.

f(wvkj)={2,j=1,

1,2≤j≤n.

此时，各点的色集合的补集为：

当i≡0(mod4)或i≡1(mod4)时：

{5},2≤j≤n,1≤i≤k-1.

当i≡2(mod4)或i≡3(mod4)时：

{5},2≤j≤n,1≤i≤k-1.

点ukj的色集合的补集分以下四种情况：

当k≡0(mod4)时：

{3},2≤j≤n.

当k≡1(mod4)时：

当k≡2(mod4)时：

{4},2≤j≤n.

当k≡3(mod4)时：

显然， 对∀uv∈E(G),有C(u)≠C(v)，故结论成立.

定理3 设Cn是n(n≥4)阶的圈图，则有

6,n≡1(mod2),(k≥3).

证明下面分两种情况讨论：

f(uij)={1,j≡1(mod2),

2,j≡0(mod2),1≤i≤k;1≤j≤n.f(w)=5.

f(u1ju1,j+1)=3,1≤j≤n-1.f(u11u1n)=3.

边uijui+1,l的染法分以下四种情况：

当i≡0(mod4)时：

f(uijui+1,j-1)=3,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=3,1≤i≤k-1;1≤j≤n-1.

当i≡1(mod4)时：

f(uijui+1,j-1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={〗3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;1≤j≤n-1.

当i≡2(mod4)时：

f(uijui+1,j-1)=4,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=4,1≤i≤k-1;1≤j≤n-1.

当i≡3(mod4)时：

f(uijui+1,j-1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;1≤j≤n-1.

f(uinui+1,1)={3,i≡0(mod4)或i≡3(mod4),

4,i≡1(mod4)或i≡2(mod4),

1≤i≤k-1.

f(ui1ui+1,n)={3,i≡0(mod4)或i≡1(mod4),

4,i≡2(mod4)或i≡3(mod4),

1≤i≤k-1.

f(wvkj)={1,j≡0(mod2),

2,j≡1(mod2),1≤j≤n.

此时，各点的色集合的补集为：

当i≡0(mod4)或i≡1(mod4)时：

{5},j≡0(mod2),1≤i≤k-1;1≤j≤n.

当i≡2(mod4)或i≡3(mod4)时：

{5},j≡0(mod2),1≤i≤k-1;1≤j≤n.

点ukj的色集合的补集分以下四种情况：

当k≡0(mod4)时：

{4},j≡1(mod2),1≤j≤n.

当k≡1(mod4)时：

当k≡2(mod4)时：

{4},j≡0(mod2),1≤j≤n.

当k≡3(mod4)时：

显然， 对∀uv∈E(G),有C(u)≠C(v),故结论成立.

2,j≡0(mod2),1≤i≤k;1≤j≤n-1.由图的结构知，|C(w)|≥4，下面分两种情形考虑：

情形2.1：当|C(w)|=4时，则点uij(除了u1j)和点w在邻点强可区别E-全染色的条件下，必存在j∈{1,2,…,n}，使得C(u1j)=C(u1,j+1)与定义矛盾.

f(uij)={1,j≡1(mod2),

2,j≡0(mod2)1≤i≤k;1≤j≤n-1.f(uin)=3,1≤i≤k.f(w)=4.

f(u1ju1,j+1)={3,1≤j≤n-2,

5,j=n-1,f(u11u2n)=f(u1nu21)=f(u11u1n)=2.

f(u1ju2,j-1)={3,j≡0(mod2),

4,j≡1(mod2),2≤j≤n.

f(u1ju2,j-+)={3,j≡0(mod2),

4,j≡1(mod2),1≤j≤n-2.f(u1,n-1u2,n)=1.

边uijui+1,l的染法如下：

f(uijui+1,j-1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1;2≤j≤n-1.

f(ui1ui+1,n)=f(uinui+1,1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1.

当k≡0(mod4)或k≡2(mod4)时：

f(wvkj)={2,j≡1(mod2),

1,j≡0(mod4),

1≤j≤n.

当k≡1(mod4)时：

f(wvkj)=6,1≤j≤n.

当k≡3(mod4)时：

f(wvkj)=5,1≤j≤n.

此时，各点的色集合的补集为：

{4,5,6},j≡0(mod2),

1≤j≤n-2.

{4,5},j≡1(mod2),

1≤j≤n-2.

当i≡0(mod4)时：

{3,4,6},2≤j≤n-2,

3≤i≤k-1.

当i≡1(mod4)时：

{3,4},2≤j≤n-2,

3≤i≤k-1.

当i≡2(mod4)时：

{3,4,5},2≤j≤n-2,

3≤i≤k-1.

当i≡3(mod4)时：

{3,4},2≤j≤n-2,

3≤i≤k-1.

当k≡0(mod4)时：

{3,6},3≤j≤n-2.

当k≡1(mod4)时：

{φ},3≤j≤n-2.

当k≡2(mod4)时：

{3,5},3≤j≤n-2.

当k≡3(mod4)时：

{φ},3≤j≤n-2.

显然， 对∀uv∈E(G),有C(u)≠C(v),故结论成立.

[参考文献]

[1]Bondy J A. Graph theory with applications [J]. Journal of the Operational Research Society, 1977, 28(1):237-238.

[2]Zhang Z,Liu L,Wang J.Adjacent strong edge coloring of graphs [J].Applied Mathematics Letters,2002,15(5):623-626.

[3]张忠辅,陈祥恩,李敬文,等.关于图的邻点可区别全染色[J].中国科学,2004,34(5):574-583.

[4]张忠辅,程辉,姚兵,等.图的邻点强可区别的全染色[J].中国科学,2007,37(9):1073-1082.

[5]顾忠栋.若干图的邻点强可区别E-全染色[D].兰州:兰州交通大学,2017.

[6]张忠辅,李敬文,田双亮,等.圈的Mycielski图的均匀全染色[J].兰州交通大学学报,2003, 22(6):1-3.

[7]强会英,晁福刚,张忠辅.完全图的广义Mycielski图的邻点可区别的全色数[J].兰州大学学报:自然科学版,2006,42(2):99-101.