图和的Mycielski图的邻点可区别I-全染色

顾忠栋，强会英，魏邦魁

(兰州交通大学数理与软件工程学院，甘肃兰州 730070)

顾忠栋，强会英，魏邦魁

(兰州交通大学数理与软件工程学院，甘肃兰州 730070)

应用构造染色法研究了图和的Mycielski图的邻点可区别I-全染色，并得到了其邻点可区别I-全色数，进一步验证了图的邻点可区别I-全染色猜想．

k方图；Mycielski图；邻点可区别I-全染色；邻点可区别I-全色数

Noga Alon在2002年数学国际大会上作了“离散数学方法与挑战”的大会报告后，图的染色成为一个很活跃、很新颖的研究领域．染色理论[1]在物理、化学、新型计算机设计、计算机图像处理、网络理论、社会科学等方面有着广泛应用．为此，许多研究者提出了一系列染色．1993年，Burris[2]首先提出了点可区别边染色概念．张忠辅等[3-5]2002年在点可区别边染色的基础上提出了邻点可区别边染色的概念，于 2004年提出了具有广泛应用背景的邻点可区别全染色概念，并于2008年进一步提出了图的邻点可区别I-全染色概念．在文献[6]中杨随义等得到了两类3-正则Halin图的邻点可区别I-全染色．本文结合了上述研究，得到了两类k方图的Mycielski图的邻点可区别I-全染色．

1 相关概念和基础

定义1[5]对图G( V,E)，映射f: V( G)∪E( G)→｛1,2,···,k｝，其中k为正整数，如果f满足：

1）对任意uv∈E( G),u≠v ，有f( u )≠f( v)；

2）对任意uv,uw∈E( G),v≠w ，有f( uv)≠f( vw) ；

3）对任意uv∈E( G),u≠v ，有C( u)≠C( v)，其中C( u)=｛f( u)｝∪｛f( uv)|uv∈E( G)｝.则称f为图G的邻点可区别 I-全染色（简记为k-I-AVDT ），而称?(=mink| G 有 k-I-AVDT ｝为G的邻点可区别I-全色数．其中是点u的色集合C( u)相对于色集合色C=｛1,2,···,k ｝的补集．

引理 1[6]对任意连通图G且，则有．若图有相邻的最大度点，则，其中Δ为图G的最大度．

猜想1[6]对于阶数不小于2的简单连通图G，则有

定义2[7]对图G( V,E)，M( G)称为图G的Mycielski图，其中：

定义3[8]对图G( V,E)和自然数k，若则称图kG 为图G的k方图．

本文未加说明的符号和术语参考文献[9-10]．

2 主要结论和证明

定理1 设 Pn是n个点的路（n≥4），则

下面分两种情况证明．

情况1 4≤n≤8时，分五种情况证明：

给出它的一个6- I- AVDTC ，令f如下：

此时f的色集合如下：

给出它的一个7-I-AVDTC ，令f如下：

此时f的色集合如下：

给出它的一个8-I-AVDTC ，令f如下：

此时f的色集合如下：

给出它的一个9-I-AVDTC ，令f如下：

对于其它边uivj有

此时f的色集合如下：

给出它的一个n-I-AVDTC ，下面分两种情况证明：

情况2.1 当n≡0(mod2)时，令f如下：

对于其它边uivj有

此时f的色集合如下：

且1≤j≤n-1，C( vn)=｛1,n-2,n-4,n｝．

情况2.2 当n≡1(mod2)时，令映射f如下：

对于其它边uivj有

此时f的色集合如下：

且1≤j≤n-1，C( vn)=｛1,n-2,n-4,n｝．

定理2 设Cn是n个点的圈（n ≥ 4），则

下面分三种情况证明．

情况2 当5≤n≤8时，分四种情况证明．

给出它的一个9-I-AVDTC ，令映射f如下：

对于其它边uivj有

此时f的色集合如下：

给出它的一个9-I-AVDTC ，令f如下：

此时f的色集合如下：

给出它的一个9-I-AVDTC ，令f如下：

对于其它边uivj有

此时f的色集合如下：

给出它的一个n-I-AVDTC ，分两种情况证明：

情况3.1 当n≡0(mod2)时，令f如下：

对于其它边uivj有

此时f的色集合如下：

情况3.2 当n≡1(mod2)时，令f如下：

对于其它边uivj有

此时f的色集合如下：

综上可知，结论成立．

[1] Bondy J A,Marty U S R. Graph theory with applications [M]. New York: The Macmillan Press Ltd,1976: 91-131.

[2] Burris A C,Schelp R H.Vertex-distinguishing proper edge-coloring [J]. J of Graph Theory,1997,26(2): 73-82.

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

[4] Zhang Z F,Chen X E,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.

[5] Zhang Z F,Woodall D R,Yao B,et al. Adjacent vertex-distinguishing I-total coloring of graphs [EB/OL]. 2008-06-12. http://202.201/18.40.8080/mas/5.

[6] 田京京．若干多重Mycielski图的邻点可区别I-全染色[J]．计算机工程与应用（自然科学版），2012，48（25）：39-41.

[7] 孔令峰，苏文龙，罗海鹏，等．的Mycielski图的邻点强边色数和邻点可区别全染色[J]．广西科学，2008，15（1）：4-6.

[8] 杨随义，何万生，何建伟．两类3-正则Halin图的邻点可区别I-全染色[J]．西南大学学报（自然科学版），2011，33（12）：98-102.

[9] 田双亮，李敬文，张忠辅．和的均匀邻强边色数[J]．数学的实践与认识，2006，36（3）：244-248. [10] Bondy J A,Murty U S R. Graph theory [M]. New York: New York Spring,2008: 101-110.

The Study of Adjacent Vertex-Distinguishing I-total Coloring of Mycielski Graph withand

GU Zhongdong,QIANG Huiying,WEI Bangkui
(College of Mathematics,Physics and Software Engineering,Lanzhou Jiaotong University,Lanzhou,China 730070)

The paper applies the structure staining method to study the adjacent vertex-distinguishing I-total coloring of Mycielski graph ofand. And the adjacent vertex-distinguishing I-total chromatic of Mycielski graph ofandis obtained thereby. The conjecture of the adjacent vertex-distinguishing I-total coloring graph is further verified in this paper.

K-square Graph; Mycielski Graph; Adjacent Vertex-distinguishing I-total Coloring; Adjacent Vertex-distinguishing I-total Chromatic Number

O157.5

：A

：1674-3563(2017)01-0030-09

10.3875/j.issn.1674-3563.2017.01.004 本文的PDF文件可以从xuebao.wzu.edu.cn获得

(编辑：封毅)

2015-09-24

国家自然科学基金(11401038)

顾忠栋(1990- )，男，甘肃武威人，硕士研究生，研究方向：图论与组合优化