若干个C3并的点可区别V-全染色

马宝林,张振亮,姚瑞

（河南科技学院,河南新乡453003）

若干个C3并的点可区别V-全染色

马宝林,张振亮,姚瑞

（河南科技学院,河南新乡453003）

根据简单图的点可区别V-全染色的概念及其染色方法,讨论若干个阶为3的圈的顶点不交并的点可区别V-全染色,并给出其全色数及染色方案,为进一步探讨mCn的点可区别V-全染色提供了理论证据,丰富了图的点可区别V-全染色的结果.

简单图；全色数；点可区别V-全染色；圈的顶点不交并

张忠辅、陈祥恩等于2004年在图的全染色概念的基础上提出了邻点可区别全染色概念[1],2008年,他们又在点可区别正常全染色的基础上提出了图的点可区别一般全染色[2].本文将从简单图的点可区别V-全染色的定义出发,讨论mC3的点可区别V-全染色并给出其全色数及证明．

1 相关概念

文献[1]和[2]中给出了简单图的点可区别正常全染色的研究,并用表示图的点可区别全色数.

定义1设G为一个阶不小于2的简单连通图,k是一个正整数,A：{1,2,…,k}为一个色集合,如果以下3个条件被满足：（v）对uv∈E（G）,有f( u)≠f( v)；（e）对uv,vw∈E（G）,u≠w,有f( uv)≠f( vw)；（i）对uv∈E（G）,有f( u)≠f( v)≠f( uv ).则f称为G的正常全染色．

上述条件中,若只满足其中一个或两个条件时就被称之为图的一般全染色.本文仅考虑只满足（e）和（i）时的情形.

定义2设G是一个简单图,k是正整数,f是一个从V（G）∪E（G）到集合{1,2,…,k}的映射,对图G的一个全染,用C（u）表示点u和它所关联的边所染的颜色组成的集合.若对于G的任意两点u和v,都有C（u）≠C（v）,则称是图G的点可区别V-全染色,简称为图G的VDVT染色.

图G的一个VDVT染色所需要的最少颜色的数目称为图G的点可区别V-全色数,记为(G).

2 图mC3的点可区别V-全染色

由点可区别V-全染色的定义可知,所有顶点的色集合均为3-组合.当n≥3时,可以将所有与n关联的3-组合用矩阵Mn给出：

（未写出的元素均为空集φ）．

定义3在矩阵Mn中,任取3个元素（不能是空集）,并按其原来顺序构成的矩阵,称为矩阵Mn的一个子块；若Mn的一个子块恰好可以完成一个C3的点可区别V-全染色,则称这个子块为一个好子块,记为I.

若将矩阵Mn中所有好子块去掉后,剩余元素构成的集合成为余集,记为An．

下面给出几种常用的好子块,如下图所示,并给出它们的一般表达式及其对C3的点可区别V-全染色方案：

I1,易知色集合{s,t,k},{k,s+1,t+1},{t+1,k,s}可以完成一个C3的VDVT染色；

I2,易知色集合{t,s,k},{k,t+1,s+1},{s+1,k,t}可以完成一个C3的VDVT染色；

I3,易知色集合{s,k,t},{t,s+1,k},{k,t+1,s}可以完成一个C3的VDVT染色；

I4,易知色集合{k,s,t+1},{t+1,k,s+1},{s+1,t,k}可以完成一个C3的VDVT染色；

I5,易知色集合{s+1,s,k},{k,s+3,s+2},{s+2,k,s+1}可以完成一个C3的VDVT染色．

引理2对任意正整数n（n≥3）构成的矩阵Mn,均可拆分为若干个好子块的并,并且其余集所含元素的个数不大于1．

特别地,当n=3m（m≥1）时,剩余一个元素；当n=3m+1（m≥1）时,无剩余元素；当n=3m+2（m≥1）时,也无剩余元素,并且当所余元素累积到3个时,恰好可以构成一个好子块．

证明：当n=3时,M3=（1,2,3）,={{1,2,3}}；

当n=5时,M5

即M7=

当n=8时,M8

当n=9时,M9=

易知A3∪A6∪A9={{2,3,1},{1,9,4},{4,6,2}},恰好可以完成一个C3的VDVT染色．

综上,当n≥10时,在上述拆分的基础上递推,并分3种情况讨论.假定前n＜3k时,引理2成立,则：

（1）当n=3k时,先根据M3k-2的结构拆分矩阵M3k的后3k-4行元素,再考虑拆分前两行元素.因为M3k共有3k-2列,则前两行元素中可以拆分为

当k=3（3m-2）（,m≥1）时,将F拆分为{1,2,3k}∪I2∪I1,

当k=3（3m-1）（,m≥1）时,将F拆分为I1∪{1,4,3k}∪I4,

当k=3（3m）（,m≥1）时,将F拆分为I1∪{1,4,3k}∪I4,

易知A3(3m-2)∪A3(3m-1)∪A3(3m)={{2,3(3m-2),1},{1,3(3m),4},{4,3(3m -1),2}},恰好可以完成一个的VDVT染色.

（2）当n=3k+1时,先根据M3k-1的结构拆分矩阵M3k+1的后3k-3行元素,再考虑拆分前两行元素.因为M3k+1共有3k-1列,则前两行元素可以拆分为I1∪(k-1)(I2∪I1)．

因此,M3k+1可以拆分为个好子块,并且没有剩余元.

（3）当n=3k+2时,先根据M3k的结构拆分矩阵M3k+2的后3k-2行元素（会剩余一个元素）,再考虑拆分前两行元素.因为M3k+2共有3k列,此时,可分为3种情况：

当k=3（3m-2）,（m≥1）时,前两行与剩下那个元素{3,4,3k}可拆分为,显然{1,2,3k+2},{2,3,3k+2},{3,4,3k}可以完成一个C3的VDVT染色；

当k=3（3m-1）,（m≥1）时,前两行与剩下那个元素{4,6,3k+2}可拆分为I1∪{2,5,3k+2}∪I2∪{2,6,3k+2}∪（k-2）（I2∪I1）∪{4,6,3k+2},显然,{2,5,3k+2},{3k+2,4,6},{6,3k+2,2}可以完成一个C3的VDVT染色；

当k=3（3m）,（m≥1）时,前两行与剩下那个元素{3,6,3k+2}可拆分为∪（k-3）（I2∪I1）∪{4,6,3k+2}显然,{2,5,3k+2},{3k+2,3,6},{6,3k+2,2}可以完成一个C3的VDVT染色；

因此,M3k+2可以拆分为个好子块,并且没有剩余元.

综上,引理成立.

由引理2,若每个好子块均为一个C3的点可区别V-全染色,则可得到mC3的点可区别V-全染色,容易推出下面定理.

3 小结

本文根据图的点可区别V-全染色的概念,给出m个阶为3的圈的并的点可区别V-全染色,并利用归纳法给出了完整的证明,为进一步探讨更高阶的圈的并的染色问题提供了思想方法,丰富了图的点可区别全染色的结论,为解决排课表问题、通讯网等实际问题给出了有力的理论依据.

[1]Zhang Z F,Chen X E.On adjacent-vertex-distinguishing total coloring of graphs[J].Science in China（Ser A）,2005,48（3）：289-299.

[2]陈祥恩.n-方体的点可区别全色数的渐进性态[J].西北师范大学学报：自然科学版,2005,41（5）：1-3.

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

[4]马宝林,刘娟,陈祥恩.图mP2与mP3的点可区别E-全染色[J].读写算,2010（9）：201-202.

[5]Ma B L,Chen X E,Liu J.2-distance coloring of strong product of graphs[J].山东大学学报,2010,45（3）：66-70.

[6]Zheng Z F,Qiu P X,Xu B G,et al.Vertex-distinguishing total colorings of graphs[J].Ars Combinatoria,2008（87）：33-45.

[7]马宝林.完全图的点可区别V-全染色[J].河南科技学院学报：自然科学版,2011,39（5）：44-46.

[8]马宝林.关于路的并的点可区别V-全染色[J].河南科技学院学报：自然科学版,2012,40（3）：65-68.

（责任编辑：卢奇）

Vertex distinguishing V-total chromatic on number of mC3

Ma Baolin,Zhang Zhenliang,Yao Rui
（Henan Institute of Science and Technology,Xinxiang 453003,China）

According to definition and method of vertex-distinguishing,V-total coloring,the vertex-distinguishing V-total coloring of the vertex-disjoint union of mC3were discussed mainly and gave vertex-distinguishing V-total chromatic number,which provided a theoretical evidence for prospective studies of mCn vertex-distinguishing V-total coloring and enriched results of graph vertex-distinguishing V-total coloring.

simple graph；chromatic number；Vertex-distinguishing V-total coloring；the vertex-disjoint union of circles.

O157.5

A

1008-7516（2013）06-0025-04

10.3969/j.issn.1008-7516.2013.06.007

2013-09-04

河南省教育科学“十二五”规划项目（2013-JKGHD-0349）

马宝林（1978-）,男,回族,甘肃张家川人,硕士,副教授.主要从事图论、数学文化研究.