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

李雨虹, 强会英, 王洪申

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

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

李雨虹1, 强会英1, 王洪申2

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

应用反证法和构造染色函数法研究了图Mk(Fn)和Mk(Wn)的邻点强可区别E-全染色,并得出了其邻点强可区别E-全色数.

邻点强可区别全染色;k重Mycielski图; 邻点强可区别E-全染色

0 引言

图论在网络设计、信息科学、密码学、DNA的基因普的确定和计数等领域有着广泛的应用. 其中图的染色问题是图论中的经典问题之一，它源自四色定理猜想以及哈密顿等问题的出现，其在组合分析和实际生活中也有着广泛的应用.1993年，Burris A C和Schelp R H首先提出了点可区别边染色的概念及猜想[1]；2002年，张忠辅，刘林忠等人提出了邻强边染色的概念以及猜想[2]；2005年，张忠辅和陈祥恩又提出了具有广泛应用背景的图的邻点可区别全染色的概念以及猜想[3]；2008年，张忠辅，程辉等人从实际问题出发，进一步提出图的邻点强可区别全染色的概念及猜想[4]；2010年，程辉和王志勇等人根据图的邻点强可区别全染色提出了邻点强可区别EI-全染色的概念[5]. 本文在此基础上，得到了两类特殊图Mk(Fn)和Mk(Wn)的邻点强可区别E-全染色，并得出了其相应的染色数.

1 预备知识

定义1[6]设图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≠w,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[6]设图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).

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

定义3[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}.

2 主要结论

由图的结构知,|C(w)|≥4,下面分两种情形考虑:

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

情形2 当|C(w)|=5时,必存在j∈{1,2,…,n}, 使得C(ukj)=C(w), 与定义矛盾.

f(ui1)=1,1≤i≤k.f(w)=6.f(u1ju1,j+1)=1, 2≤j≤n-1.

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

f(u1ju2,j-1)=5, 3≤j≤n.f(u1ju2,j+1)=5, 2≤j≤n-1.

当k≡1(mod4)或k≡2(mod4)时f(wvkj)=4, 1≤j≤n.

此时,各点色集合的补集为:

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

定理2 设Wn是n(n≥4)阶的轮图,则有

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

由图的结构知,|C(w)|≥5,下面分两种情形考虑:

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

情形1.2 当|C(w)|=6时,必存在j∈{1,2,…,n}, 使得C(ukj)=C(w), 与定义矛盾.

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

f(u1ju21)=2,j=n-1;n.f(u1ju2,j-1)=1, 3≤j≤n.

f(u1ju2,j+1)=1,2≤j≤n-1.

此时,各点的色集合的补集为:

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

f(ui1)=1,1≤i≤k.f(w)=6.f(u1ju1,j+1)=1,2≤j≤n-1.

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

f(u1ju2,j-1)=5, 3≤j≤n.f(u1ju2,j+1)=5,2≤j≤n-1.

当k≡1(mod4)或k≡2(mod4)时f(wvkj)=4, 1≤j≤n.

此时,各点色集合的补集为:

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

[1] Burris A C. Vertex-distinguishing edge-colorings[D].Memphis State University,1993.

[2] Zhong Z F,Liu Z L,Jiang F W. Adjacent Strong Edge-Coloring of Graph[J]. Applied Mathematic letter,2002,15(5):623-626.

[3] Zhang Z F,Chen X G,Li J W,et al. On adjacent vertex-distinguishing total coloring of graphs[J]. Science in China: Ser A Mathmatics,2005,48(3): 289-299.

[4] Zhang Z F,Chen X G. On adjacent-vertex-strongly-distinguishing total coloring of graphs[J]. Science in China.Series A: Mathmatics,2008,51(3): 427-436.

[5] Chen X G,Wang Z Y. Adjacent vertex-strongly-distinguishingE-total coloring of graphs[J]. Shan dong Univ Nat Sci,2010(6):18-22.

[6] 顾忠栋,强会英,魏邦魁.两类特殊图的邻点强可区别E-全染色[J].苏州科技学院学报(自然科学版).2016,35(3):18-21.

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

OnAdjacentVertexStronglyDistinguishingE-totalColoringofTwoclassesk-multi-MycielskiGraphs

LI Yu-hong1, QIANG Hui-ying1, WANG Hong-shen2

(1.School of Mathematics, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China)(2.School of Mechatronic Engineering, Lanzhou University of Technology, Lanzhou Gansu 730050, China)

The adjacent vertex strongly distinguishingE-total coloring ofk-multi-Mycielski Graphs ofMk(Fn)andMk(Wn) are givening by contradiction and constructing colorable function, meanwhile, the adjacent vertex strongly distinguishingE-total chromatic of them are obtained.

adjacent vertex strongly distinguishing total coloring;k-multi-Mycielski graphs; adjacent vertex strongly distinguishingE-total coloring

O157.5

A

1671-6876(2017)03-0205-05

[责任编辑李春红]

2017-06-06

国家自然科学基金资助项目(11461038; 11561042)

强会英(1968-),女,甘肃白银人,教授,研究方向为图论与组合优化. E-mail: qhy2005ww@126.com