图Dn,4的邻点强可区别的全染色

张东翰

（商洛学院 数学与计算机应用学院，陕西商洛726000）

图Dn,4的邻点强可区别的全染色

张东翰

（商洛学院 数学与计算机应用学院，陕西商洛726000）

通过分析图Dn,4的结构，利用穷举法和组合分析法讨论了图Dn,4的邻点强可区别的全染色，通过构造具体染色得到了图Dn,4的邻点强可区别的全色数。从而证明了图Dn,4的邻点强可区别的全色数是存在的。

穷举法；组合分析法；色数

张忠辅教授提出了图的邻点强可区别的全染色的概念[1]，随后很多学者对其进行了研究，迄今，刘永平等[2]给出了Pn×Pm的邻点强可区别的全染色，卢建立等[3]给出了中间图的邻点强可区别的全染色，郭旭卫等[4-5]给出了一类Pm×Cn图和D(Pn)图的邻点强可区别的全染色，郑纯等[6]给出了扇和轮的邻点强可区别的全染色，张效贤[7]给出了C3m×C3n、C4m×C4n的邻点强可区别的全染色，但是，由于此染色的难度比较大，相关结果并不是很多，通过对大量文献的研读，研究了图Dn,4的邻点强可区别的全染色。

1 预备知识

定义1[1]设G(V,E)是阶数不小于3的简单连通图，k是自然数，f是从V(G)∪E(G)到{1,2,…,k}的映射，如果满足：

1)对任意的边uv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)≠f(v)；

2)对任意的两相邻的边uv,uw∈E(G)(v≠w)，f(uv)≠f(uw)；

3)对任意的边uv∈E(G)，其端点的色集合满足C(u)≠C(v)，其中任一顶点v的色集合为C(u)={f(u)}∪{f(v)｜uv∈E(G)}∪{f(uv)｜uv∈E(G)}。则称f为图G的一个邻点强可区别的全染色，（简记为k-AVSDTC），且称数χast(G)=min{k｜k-AVSDTC}为G为的邻点强可区别的全色数。

定义2[8]由点集V(Dn,4)={v0,v11,v12,v13,v21,v22, v23,…,vn1,vn2,vn3}和边集E(Dn,4)={v0v11,v11v12,v12v13, v13v0,v0v21,v21v22,v22v23,v23v0,…,v0vn1,vn1vn2,vn0v0}所形成的图，记为Dn,4。

引理1[1]设图G是阶不小于3的图，有χast(G)≥Δ+1；若G有相邻的两个最大度点，则χast(G)≥Δ+2，其中Δ代表图G的最大度。

本文中未加叙述的术语、记号可在文献[9-15]中找到。

2 定理及其证明

定理1对于图Dn,4，有。

证明当n=1时，此时图是一个4阶的圈，根据文献[1]可知χast(Dn,4)=5。

当n≥2时，由于没有相邻的最大度点，所以根据引理1可知χast(Dn,4)≥2n+1，现给出一个(2n+ 1)-AVSDTC，设色集合C={1,2,3,…，2n，2n+1}。

对于边v0v11,v0v13,v0v21,v0v23,…,v0vn1,v0vn3,分别用色1,2,3,…，2n染，对于边vi1vi2,vi2vi3分别用色1,2染(i=2,3,…，n)，对于边v11v12,v12v13分别用色3,4染。

对于点v0,vi2(i=1,2,…，n)都用色2n+1染，对于点vi1,vi3(i=1,2,…，n)分别用色4,3染,则此染色法显然是一个正常的全染色，又由于C(v0)={1,2,3,…,2n,2n+1}，C(v11)={1,3,4,2n,2n+1}，C(v12)={3,4,2n+1}，C(v13)={2,3,4,2n+1}，C(vi1)={1,4,2i-1,2n+1}，C(vi2)={1,2,3,4,2n+1}，C(vi3)={2,3,2i,2n+1}，(i=2,3,…，n)。因此该染色法是一个(2n+1)-AVSDTC，即χast(Dn,4)=2n+1。

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

[2]刘永平,张 锐,苏旺辉,等.Pn×Pm的邻点强可区别的全染色[J].兰州理工大学学报,2007,33(2)：164-167.

[3]卢建立,任凤霞,马美琳.中间图的邻点强可区别的全染色[J].河南师范大学学报：自然科学版,2012,40(5)：112-114.

[4]郭旭卫,马 刚,马少仙.一类Pm×Cn图的邻点强可区别全染色[J].贵州大学学报：自然科学版,2009,26(2)：24-26.

[5]郭旭卫,马少仙.D(Pn)图的邻点强可区别全染色[J].甘肃联合大学学报：自然科学版,2009,23(5)：24-25.

[6]郑 纯,刘焕平.扇和轮的邻点强可区别全染色[J].哈尔滨师范大学学报：自然科学版,2009,25(5)：33-34.

[7]张效贤.C3m×C3n、C4m×C4n的邻点强可区别全染色及全色数[J].甘肃科学学报,2009,21(2)：26-28.

[8]孙婷婷.图的点可区别的边染色及点可区别的全染色[D].重庆：重庆大学,2008.

[9]王彦妮,王丽伟,刘 萍.几类图的邻点可区别的全染色[J].科学技术与工程,2007,7(13)：3048-3051.

[10]闫丽红,王治文,张忠辅.θ-广义图的邻点可区别的全染色[J].经济数学,2007,24(1)：103-106.

[11]陈祥恩,张忠辅.Pm∨Pn的邻点可区别的全染色[J].西北师范大学学报,2005,41(1)：13-15.

[12]张东翰.蛛形图的全染色和星全染色[J].商洛学院学报,2013,27(6)：31-32.

[13]张东翰,朱 白.路的D(3)-点可区别的全染色[J].商洛学院学报,2014,28(2),11-12.

[14]Bondy J A,Murty U S R.Graph theory with Applications[M].New York：The Macmillan Press Ltd, 1976.

[15]Reinhard D.Graph theory[M].New York：Springer-Verlag,1997.

（责任编辑：李堆淑）

Adjacent Vertex Strongly Distinguishing Total Coloring of Graph Dn,4

ZHANG Dong-han
(College of Mathematics and Computer Application,Shangluo University,Shangluo 726000,Shaanxi)

Through the analysis of graph Dn,4,the adjacent vertex strongly distinguishing total coloring of graph Dn,4is discussed by the exhaustion method and the combination analytic method.The adjacent vertex strongly distinguishing total chromatic number of graph Dn,4is gained by construction specific coloring,thus,the adjacent vertex strongly distinguishing total chromatic number of graph Dn,4is existent.

method of exhaustion;combination analytic method;chromatic number.

O157.5

：A

：1674-0033（2014）06-0008-02

10.13440/j.slxy.1674-0033.2014.06.003

2014-09-23

陕西省教育厅专项科研计划项目（14JK1225）

张东翰，男，河北邢台人，硕士，讲师