两类3-正则图的邻点可区别E-全染色.pdfVIP

第38卷第3期 西南师范大学学报(自然科学版) 2013年3月 of Normal ScienceEdition)Mar．2013 V01．38No．3 SouthwestChina Journal University(Natural 文章编号：1000—5471(2013)03—0036—06 两类3一正则图的邻点可区别E一全染色① 杨随义， 邵海琴， 何万生 天水师范学院数学与统计学院，甘肃天水741001 摘要：应用构造具体染色的方法得到了两类3一正则图的邻点可区别E一全色数，进一步验证了关于图的邻点可区 别E一全染色的猜想． 关键词：E一全染色；邻点可区别E一全染色；邻点可区别E一全色数 中图分类号：0157．5 文献标志码：A 图的染色是图论的重要研究内容之一，由计算机科学和信息科学等所产生的点可区别边染色[1]、邻点 可区别边染色(或邻强边染色)c2 别j一全染色H¨等都是十分困难的问题，至今文献甚少．在此基础之上，张忠辅等人进一步提出了图的新染 色概念．图的邻点可区别E一全染色是其中之一”]，本文给出了两类3一正则图的邻点可区别E一全色数． r63 定义l 设G是阶至少为2的连通图，k为正整数，，是图G的使用颜色为1，2，…，k的正常全染 染色厂下点z的色集合．如果V G有k一邻点可区别全染色)为G的邻点可区别全色数． 托(G)一min{k 定义2[73设G是阶至少为2的连通图，．厂是图G的使用颜色为1，2，…，k的全染色．如果G的任意 相邻的点染不同的颜色，并且G的任意点与该点相关联的所有边的颜色不同，那么称厂为G的E一全染色． 的集合，称之为在厂下点z的色集合．如果对V 别E一全染色(简记为k-AVDET染色)．称‰e(G)一min{kG有k一邻点可区别E一全染色)为G的邻点可 区别E一全色数． 在本文中，考虑了两类3一正则图G；，…和R；…。的邻点可区别E一全染色． 定义3[81设k，m，九均为正整数，且n一2—1·3足，图G；．。，。的定义如下： 州 V(Gt．。，。)一{73。，it一1，2，…，k)UU{“：，}歹一1，2，…，2’1·3志)； i=l 卅1 E(G女．卅．。)一{u。，M1．3f2，勘ofHl．3卜l，73。f钍1+3ft一1，2，…，k)UU{H”“：+1，2，1，“，，M汁1．2，IJ一1，2，…， l=l 2‘一1·3是)U{“。，“。，，一。lJ一1，2，…，竹——1}U{“。lUmn)． 定义4[83设是，m，行均为正整数，且是≥3，挖一2—1·点，图R。…。的定义如下： m V(R^…。)一{73。，lt一1，2，…，志)UU{“：，IJ一1，2，…，2’一·志)； ①收稿日期：2011—06—20 基金项目：甘肃省自然科学基金(096RJZEl06)；天水师范学院中青年教师科研资助项目(TSY201206) 作者简介：杨随义(1977一)，男，甘肃天水人，硕士，副教授，主要从事代数图论与染色． 万方数据 第3期 杨随义，等：两类3一正则图的邻点可区别E一全染色 37 ————————————————————————————————————————————————————————————二～ “i“一．2J J歹一1，2，…，2。1·是}U{“。M…一。I歹一1，2，…，”一1}U{“。。‰，}． 图1及图2分别画出了G∽一；及R。．…