若干图的Mycielski图的点可区别均匀边色数

格式：pdf
大小：393.74 KB
文档页数：6

下载文档原格式

路的Mycielski图的[r

Ａ．ｅｉＫｍｎｔｚ和Ｍ．ｒｎｉ文献［］又提出了［，，］一着色概念，是点着色、着色、着色三种经典着Ｍａａｇｏ在１中ｒｓｔ它边全
色的推广，用也非常广泛，如一些比赛的训练安排，求既有足够的时间训练，能得到充分的休息，且应比要又而
ｕ｛Ｉ ∈ Ｇ， ∈Ｖ，删ｕ（）且 ∈ （）ｕ｛ＥＧ｝
引理１若ＨＣＧ，＿则，）（．Ｇ）（．
ＩＥ，中Ｗ甓Ｇ，ｌ ∈ Ｇ｝｝其Ｖ（）Ｖ＝｛（）．
弓理２ ¨ ｍａｒ（ｌｘ｛（Ｇ）一１）＋１ｓ（，（Ｇ）一１）＋１ｔ，＋１｝
（ ≤ （Ｇ）一１Ｃ）ｒ（）＋ｓ（（Ｇ）一１）＋ｔ＋１
引理３
对简单图Ｇ（Ｇ）（（）＝Ｇ）＋１．
２主要成果
记个顶点的路Ｐ（２的Ｍｙｉｌｋ图为（，（Ｐ）＝ＶＰ）ｃｅｓｉＰ）且（）（）ｕｕ｛｝其中（）＝｛，，Ｐ
１定义和引理
定义１ … 给定非负整数ｒｓ和ｔ且ｍａｒｓｔ１若图Ｇ（Ｅ）一个映射，，ｘ｛，，｝，，有：（ｕＥ（一｛１，，一１，Ｇ）Ｇ）０， … ｝ ∈Ｎ
满足下列条件：中相邻的点，，１（一）ｒ对Ｖ有（（１；）对Ｅ中相邻的边ｅ有ｌ（ｉ一ｅ１，ｅ（））ｉ

P 2n的Mycielski图的邻强边色数和邻点可区别全色数

维普资讯
广西科学ＧｕｎｘＳｉｃｓＯ８１（）４ａｇｉｃｎｅＯ，５１：～６ｅ２
的Ｍｙｉｓｉ的邻强边色数和邻点可区别全色数ｃｌｋ图ｅ
ＡｊｃｎｔｏｇＥｇｏｌｎａｊｃｎ－ｅｔｘｄａｅｔＳｒｎｄｅＣｌｒｙａｄＡｄａｅｔｖｒｅ。ｏ。Ｉ
ｔｔ１ｈｏｔｃｎｍｂｒＭｙｉｌｋｉｇａｈｏａｒｍａｉｕｃｅ．ｃｅｓｒｐ
图的染色是图论研究的主要内容之一，色的一染
／为Ｇ的ｋ正常边染色，为ｋＰ～记－ＥＣ．
个基本问题就是确定相应的色数．图的强边染色产生
中图法分类号：７５０１．５文献标识码：Ａ文章编号：０５９６（０８Ｏ一０４０１０ — １４２０）ｌ００ — ３
ＡｂｔａｔＡｅｇａｈｏ尸：ｓｄｆｅｔｅａｊｃｎｔｏｇｅｇｈｏｔｕｅｎｄａｅｔｓｒｃ：ｎｗｒｐｆｗａｅｉｄ，ｈｄａｅｔｓｒｎｄｅｃｒｍａｉｎｍｂｒａｄａｊｃｎｎｃｖｒｅｉｔｇｉｉｇｔｔｌｈｏｔｕｅ，ｎｏｓｒｃｈｏｏｉｇｍｅｈｄｏｄａｅｔｖｒｅｅｔｘｄｓｉｕｓｎｏａｒｍａｉｎｍｂｒａｄｃｎｔｕｔｔｅｃｌｒｎｔｏｆａｊｃｎｅｔｘｎｈｃｃｄｓｉｇｉｉｇｔｔｌｏｏｉｇｏｈｒｐｆＭｙｉｌｉｆｇａｈＰ：ｌｏｂｏｆｍｅｅ ≥ ３ｉｔｕｓｎｏａｌｒｎｆｔｅｇａｈｏｃｓｒｐａｓｅｃｎｉｄｗｈｎｎｈｃｅｋｏｒ．

完全图的点可区别全染色算法

完全图的点可区别全染色算法作者：徐晓青李双元张卫平来源：《电脑知识与技术》2012年第18期摘要：设f是图G的一个正常的k-全染色，若G中任意两点的色集不同，则称f为G的k-点可区别全染色，简记为k-VDTC of G,，并称最小的k为G的点可区别全色数。

该文针对完全图的点可区别全染色的特点提出了分类顺次着色算法，该算法首先按照一定的规则对元素进行分类然后对元素进行顺次着色，同时给出关联锁表，根据关联锁表判断是否得到问题的解。

实验结果表明：该算法有效地解决了完全图的点可区别全染色问题。

关键词：k-点可区别全染色；点可区别全色数；分类顺次着色；完全图；关联锁表中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)18-4498-03Algorithm for the Vertex-Distinguishing Total Coloring of Complete GraphsXU Xiao-qing, LI Shuang-yuan, ZHANG Wei-ping(Lanzhou Jiaotong University,Lanzhou 730070,China)Abstract: Let f be a proper k- total coloring of a graph G , if for any two distinct vertices u and v in G,the set of colors of u differs from the set of colors of v, f is called a k-vertex distinguishing total coloring of G , is abbreviated k-VDTC of G and the minimal number k of colors required for vertex-distinguishing total coloring of G is called the vertex-distingishing total chromatic number of G.In this paper, a new algorithm whose name is algorithm of classified order coloring is proposed on the base of the characteristics of the vertex-distinguish? ing total coloring of complete graphs .All of its elements are classified according to some rules and then are colored in proper sequence in the algorithm. Moreover, a relatelocktable is presented to judge whether the result is correct. The experimental results show that the algo? rithm can effectively solve the vertex-distinguishing total coloring of complete graphs.Key words: vertex-distinguishing total coloring; vertex-distinguishing total chromatic number; classified order coloring; relatelocktable该文根据完全图的点可区别全染色的特点，设计了聚类顺次着色的算法，利用关联锁表和元素的2次幂求和对算法进行控制，使得算法有效的解决了完全图的点可区别全染色。

毕业论文范例——mycielski图的染色问题

目录中文摘要------------------------------------------------------------------2 英文摘要------------------------------------------------------------------3 引言----------------------------------------------------------------------4 一、mycielski图的定义-----------------------------------------------------5 1． mycielski图的定义----------------------------------------------------52 . 广义mycielski图的定义-----------------------------------------------5二、mycielski图的染色问题-------------------------------------------------5(一)边色数----------------------------------------------------------------51. Mycielski图的边色数---------------------------------------------------52.广义Myc ielski 图的边色数----------------------------------------------6(二)邻强边色数------------------------------------------------------------61. Myciel ski 图的邻强边色数---------------------------------------------72. 广义Mycielski 图的邻强边色数------------------------------------------7 （三）全色数--------------------------------------------------------------81. Mycielski图的全色数--------------------------------------------------82. 广义Mycielski图的全色数---------------------------------------------9 （四）邻点可区别全色数----------------------------------------------------91.Mycielski 图的邻点可区别全色数---------------------------------------102.广义Mycielski图的邻点可区别全色数----------------------------------12 致谢--------------------------------------------------------------------13 参考文献----------------------------------------------------------------14Mycielski图的染色问题摘要：本论文总结了Mycielski 图及广义Mycielski 图关于染色问题的各方面定义和定理，主要包括边色数、邻强边色数、全色数、邻点可区别全色数的相关结论。

多重Mycielski图的邻点可区别全染色

．
。
）图Ｇ的顶点集合，Ｅ（是图Ｇ的边集．是Ｇ）
Ｔｈｄａｅｔｖｒｅ — ｉｔｇｉｈｎｏａｏｏｉｇｏｅａｊｃｎｅｔｘｄｓｉｕｓｉｇｔｔｌｌｒｎｆｎｃ
ｋ－ｕｔ— ｙｉｌｋｈｒｐｍｌｉＭｃｅｓｉｔｅｇａｈｓ
ＺＨＡＮＧＣｈｅｎ，ＣＨＥＮａ — ｎ，ＬＩｎｓｅｇＸｉｎｇａＵＸｉ — ｈｎＧ有ｔＴＣＧ）ｎｔｌ —
ＡＶＤＣ）Ｔ叫做图Ｇ的邻点可区别全色数．
定义２对阶图Ｇ（Ｅ）ＭｋＧ）为Ｇ的ｋ，，（称
重Ｍｙｉｌｉ（ ≥ ２，其中（Ｇ）一｛。，ｃｓ图ｋｅｋ）Ｍ（）。
Ａｂｔａｔｓｒｃ：Ｔｈｐｅｏｎｓｏｈｄａｅｔｅｔｘ— ｉｔｇｉｈｎｏａｏｏｉｇｎｍｂｒｏｍｕｔ— ｅｕｐｒｂｕｄｆｔｅａｊｃｎｖｒｅｄｓｉｕｓｉｇｔｔｌｃｌｒｎｕｅｎｋ— ｌｉｎＭｙｉｌｋｒｐｓａｅｄｓｕｓｄＴｈｄａｅｔｅｔｘ— ｉｔｇｉｈｎｏａｏｏｉｇｎｍｂｒｎｋｍｕｔｃｅｓｉｇａｈｒｉｃｓｅ．ｅａｊｃｎｖｒｅｄｓｉｕｓｉｇｔｔｌｃｌｒｎｕｅｓｏｎｌｉ
Ｋｅｒｓ－ｌ — ｙｉｌｋｒｐｙｗｏｄ：ｋｍｕｔＭｃｅｓｉｇａｈ；ａｊｃｎｅｔｘｄｓｉｇｉｈｎｏａｏｏｉｇ；ｔｅａｊｃｎｅｔｘｉｄａｅｔｖｒｅ — ｉｔｕｓｉｇｔｔｌｃｌｒｎｎｈｄａｅｔｖｒｅ —

关于路和轮的广义Mycielski图的邻点可区别的边染色

显然，对任意一个简单图Ｇ且Ｉ（Ｉ，ＶＣ）≥３Ｇ≠Ｃ
ｆ／４ｆ
ｌｏ２；（ｄ）ｍ
（阶数为５的圈）有ｘＧ △（）如果最大度点都，（）Ｇ；相邻，ｘＧ ≥△（＋。此概念提出后，则（）Ｇ）１相关的文章陆续产生，请参见文献【— 】２３。
Ｍｙｉｓｉ。ｃｅｋ图ｌ
，
∥ ）ＩＪ３
、
、
￣ｍｄ）／一１（ｏ３；（ｏ３ｆ，ｍｄ）２
／ｏｏ）ｆ（ｄ；；ｍ３
／ｊＯ。３ｆ－（ｄ）ｍ；
设％（是一个图，Ｇ）如果点集合（（）ｏＧ）：ｈ０… ，；２，１ …，；；２ … ，位，，ｐ；且边集合 … Ｙ｝ｎ
第４期
【基础数学与应用数学研究】
关于路和轮的广义Ｍｙｉｓｉｃｅｋ图ｌ的邻点可区别的边染色
闫丽宏１治文１忠辅１，王，张，２
（．阳师范学院数学系，陕西咸阳７２０；．１咸１００２兰州交通大学应用数学研究所，肃兰州７０７）甘３００
摘
要：个图Ｇ的边染色被称为邻点可区别的。果满足图Ｇ中任意两个相邻点所关联一如
的边所染颜色的集合不同。研究了图路和轮的广义Ｍｙｉｌｉｃｓ图的邻点可区别的边染色并证明ｅｋ
它满足邻点可区别的边染色猜想。关键词：；；义Ｍｙｉｓ路轮广ｃｅｋｌｉ图；点可区别的边染色邻

一些倍图的点可区别均匀边色数

（ｎ＝（）｛，：Ｄ）（）２：：（）。＝１三５
证记（＝｛ｉ０ｌ２ …，｝Ｅ（ｎ＝｛ｏｉ，，，｝若１＝１ＦＤ（１）Ｓ） “ Ｉ＝，，，ｎ；Ｓ） “ Ｉ：１２ … ｎ．２，（Ｓ）＝Ｍ
点可区别均匀边色数．
关键词
倍图，区别均匀边染色，可区别均匀边色数点可点文献标识码Ａ
中图分类号０５．１５７
１引言及定义．
由信息科学、计算机科学、生物学等提出的点可区别边染色（或强边染色）是一个十分困难１的问题，３文［］提出了距离不超过的任意两点可区别的边染色概念及相关猜想，４提出了图的文［］邻强边染色概念，了若干结果，提出了有关猜想．得到并文献［］５得到了两个联图的点可区别边色数，
猜想２对ｌ（）３的简单连通图Ｇ，ＧｌＶ有
（）Ｇ（），Ｇ＋１且（）＝（）ＧＧ．
定义４设为简单图Ｇ的拷贝，Ｇ的顶点为，，记Ｇ相应的顶点为，若满足
（Ｇ）＝（Ｄ（）Ｇ）ＵＶＧ）（
数，表示ｎ个中取ｍ个的组和数，（）则称（）：ｍｘｒｎ０ｌ）Ｇａ｛ｉ｛（ａ
为Ｇ的组合度．猜想１－对Ｉ（）３的简单连通图Ｇ有Ｎ１３ＧｌＶ，
（）（）＋１Ｇ ≤ Ｇ．
｝ＧｉＡ（），）（ ≤ Ｇ｝
．
定义２对｝（ｌ２Ｖ）≥ 的简单图Ｇ，）点可区别边染色法厂满足（的，

完全二部图的Mycielski图的点可区别全色数

左端知（Ｍ（
）≥ ２）ｍ＋２要证结论为真，，仅
需给出Ｍ（Ｋ）的一个（ｍ＋２一）Ｃ法．２）ＶＩＴ
设Ｃ＝｛，，，ｍ＋１０．厂为１２ … ２，｝令
厂叫）一ｍ＋ｌ（；
ＵＥＧ（）Ｕ｛ＩＥＶ．删）其中，
文献标识码：Ａ
０引言
图的染色是图论的主要研究内容之一．由计算机科学和信息科学所产生的点可区别边染色＿，１邻］点可区别边染色（或邻强边染色）２及Ｄ（点可＿【叫区别全染色点可区别全染色［都是十分困难引，。等的问题，今文献甚少．文给出了完全二部图的至本
不同元素中任取个的组合数；＋１和△分别表示Ｇ
的最小度和最大度．显然，猜想的左端是成立的．
Ｍｙｉｓｉｃｌ图的点可区别全色数．ｅｋ定义１。对阶数不小于２的联通图Ｇ（Ｅ）［Ｖ，，
令－为Ｖ（厂Ｇ）ＵＥ（到Ｃ一｛，，，｝Ｇ）１２… 是的映射，其中ｋ为正整数，对任意的 “Ｅ（，表示Ｇ）Ｃ（）
厂“ （）Ｕ｛（ｖ＇Ｅ（）．ｆｕ）ｌＯ∈ ＵＧ）如果厂满足：ｉ．对任意的Ｕ，ＥＥ（，７删Ｇ）乱≠ ，３有
ｆｕ）ｆｖ；（ｖ ≠ （ｍ）
１主要结论及其证明
引理１Ｅ对Ｍ（Ｋ）有，
ｆｕ）一２（１ｍ＋１；ｆｕ）一０（ｓ；

双语教学示范课程建设项目申报表

双语教学示范课程建设
项目申报表
标准化管理部编码-[99968T-6889628-J68568-1689N]
双语教学示范课程建设项目申报表
高等数学（微积分）
课程名称（中
文）：
（英文）：Advanced Mathematics (Calculus) 课程负责人：姚兵
外语语种：英语
课程类别：专业必修课
所属专业：基础数学
所在学院：数学与信息科学学院（盖章）
联系电话：
申报时间：二〇〇九年十月十日
西北师范大学教务处制
填写要求
一、以word文档格式如实填写各项，空缺项要填“无”。

二、表格文本中外文名词第一次出现时，要写清全称和缩写，再次出
现时可以使用缩写。

三、表格空间不足的，可以扩展或另附纸张；均用A4纸打印，于左侧
装订成册。

1．课程负责人情况
2. 教学队伍情况
3
4．课程建设规划
5．说明栏。

广义Mycielski图的邻点可约边染色

Ｘ一（Ｇ）一ｍａ｛ｋ— ｘｋＩＡＶＲＣｏＥＧ）ｆ
ｄｖ）３由定义２，一（ａ ≤ ４设Ｃ：｛，，（，＝ａ知ＸＣ）．１２３４，厂为，｝令
厂（Ｖ２１Ｏ）一ｆＶｌ（ｎ砌）一１，ｆ（ｏｏ）一ｆｖ３ｖ２３Ｖ（Ｉｌ叫）一２，ｆ（ｏｏ）一ｆｖ２ｖａ１Ｖ（，．ｗ）一４．
ｖＧ）ｕｇＧ，（）（）有ｃ “ ＝Ｃ，ｆ为Ｇ的走邻点可约边染色，所用最多染色数称为图ＧＷ（，ｒＥ（）当＝ｄ时，（）（）则一其
的邻点可约边色数，文得到了若干广义Ｍｙｉｓｉ的邻点可约边染色数．本ｃｌｋ图ｅ
广义Ｍｙｉｌｋ图的邻点可约边染色ｃｅｓｉ
张园萍，强会英，孙亮萍，文飞
（兰州交通大学数理与软件工程学院，甘肃兰州７０７）３００
摘
要：简单图Ｇ（Ｅ）若存在自然数ｋ１ ≤△（）映射ｆ：Ｇ－｛，，，｝对Ｖ，，（ ≤惫Ｇ）和Ｅ（）－１２ … ｋ使得对任意相邻两点 “ －￣，
称为Ｇ的邻点可约边染色数，中：（）一｛（ｖ其Ｃ“ ｆｕ）
ｆ ∈ Ｅ（）显然ＸＧ）是存在的．删Ｇ）．一（
其它边按如下循环着色：
Ｕｎ ’ １，＇＂ｉＵ汁２Ｏｌ７１．，．ｉＵ汁１，＇２ｉ汁１３’７ｉ汁１１，３汁３７２。）１）２’ ，．３‘ ），

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

f（vn-1vn）=f（vn-2vn-1′）=1 f（vn-1vn′）=f（vnvn-1′）=2 f（v1v2）=f（vn-1vn-2′）=n f（vi′w）=i（i=1，2，…，n） f（vivi+1）=i（i=2，3，…，n-2） f（vivi+1′）=f（vi+1vi′）=i+2（i=1，2，…，n-3）此时
情形 1.1 当 n=3 时，令 C={1，2，3，4，5}构造 f 如下
f（v1v2）=f（v1′w）=1 f（v2v3）=f（v2′w）=2 f（v1v3）=f（v3′w）=3
f（v1v2′）=f（v2v3′）=f（v3v1′）=4 f（v2v1′）=f（v3v2′）=f（v1v3′）=5
此时
C（v1）={1，3，4，5} C（v2）={1，2，4，5} C（v3）={2，3，4，5} C（v1′）={1，4，5}
安常胜，冯旭霞，罗亮，崔俊峰
（兰州交通大学数理与软件工程学院，甘肃兰州 730070）
摘要：简单图 G 的正常边染色 f，若对于坌u，v∈V （G），有 C （u）≠C （v），称 f 是图 G 的点可区别边染色，其中
C（u）={f（uv） uv∈E（G）}。若满足 |Ei|-|Ej| ≤1（i，j=1，2，…，k），其中坌e∈Ei， f（e）=i（i=1，2，…，k），称 f 是图 G 的点可区别均匀边染色。讨论了若干图的 Mycielski 图的点可区别均匀边染色。
f（v1v2）=f（v1′w）=1 f（v1v2′）=f（v3′w）=f（v2v3）=2 f（v2v1′）=f（v3v2′）=3 f（v2v3′）=f（v2′w）=4
此时
C（v1）={1，2} C（v2）={1，2，3，4} C（v3）={2，3} C（v1′）={1，3}
23 i=2
C（v2′）={2，3，4} C（v3′）={2，4} C（w）={1，2，4}且|Ei|= 2 其他
第1期
安常胜等：若干图的 Mycielski 图的点可区别均匀边色数
23
≥5 n=3，4
定理 2 设 Cn 是 n 阶圈，则有 χvde′（M（Cn））= n n≥5 。
证明情形 1 当 n=3，4 时，易得 μ（M（C3））=μ（M（C4））=5。
显然，有 χvde′（M（C3））≥μ（M（C3））=5， χvde′（M（C4））≥μ（M（C4））=5，只需证明 M（C3），M（C4）有一个 5-VDEEC。
此时
C（v1）={3，5} C（v2）={1，2，3，5} C（v3）={1，2，4，5} C（v4）={4，5}
C（v1′）={1，3} C（v2′）={2，3，5} C（v3′）={1，3，5} C（v4′）={1，4}
22 i=2，4
C（w）={1，2，3，4，v∈V（M（P4）），若 u≠v，均有 C（u）≠C（v），且 |Ei|-|Ej| ≤1（i，j=1，2，3，4，5）。
23 i=1，n-1，n
C（w）={1，2，…，n} C（vi′）={i，i+1，i+2}（i=2，3，…，n-2}且|Ei|= 4 其他显然，对坌u，v∈V（M（Pn）），若 u≠v，均有 C（u）≠C（v），且 |Ei|-|Ej| ≤1（i，j=1，2，…，n）。所以，f 是 M（Pn）的一个 n-VDEEC。
所以，f 是 M（P4）的一个 5-VDEEC。
情形 3 当 n≥5 时，可求得
λ λ λ λ λ λ λ λ μ（M（Pn））=max{min{λ|
λ n
≥1}，min{λ|
λ 4
≥n-2}，min{λ|
λ 3
≥n-2}，min{λ|
λ 2
≥4}}=n
显然，有 χvde′（M（Pn））≥μ（M（Pn））=n，只需证明 M（Pn）有一个 n-VDEEC。令 C={1，2，…，n}构造 f 如下
关键词：圈；星；Mycielski 图；点可区别均匀边染色；点可区别均匀边色数
中图分类号： O157.5
MR（2000） Subject Classification： 05C15
文献标识码： A
文章编号： 1672－0687（2010）01－0021－05
图论在自然科学与应用科学中都起着重要作用，图的染色问题是图论研究的主要内容之一，具有很强的
显然，有 χvde′（M（P4））≥μ（M（P4））=5，只需证明 M（P4）有一个 5-VDEEC。
令 C={1，2，3，4，5}构造 f 如下
f（v1′w）=f（v3v4′）= f（v2v3′）=1 f（v2v3）=f（v2′w）=2 f（v1v2′）=f（v2v1′）=f（v3′w）=3
f（v3v4）=f（v4′w）=4 f（v3v2′）= f（v4v3′）=f（v1v2）=5
k），则称 f 是图 G 的点可区别均匀边染色，简记为 k-VDEEC of G，且称 χvde′（G）=min{k k-VDEEC of G}为 G
的点可区别均匀边色数。
定义 2[1~7] 对简单图 G，ni 表示具有度为 i 的点数，δ、△ 分别表示图 G 的最小度与最大度，称 μ（G）=
E（G）}，则称 f 是图 G 的点可区别边染色，简记为 k-VDEC of G，且称 χvd′（G）=min{k k-VDEC of G}为 G 的点
可区别边色数。
若 f 是图 G 的点可区别边染色，且满足 |Ei|-|Ej| ≤1（i，j=1，2，…，k），其中任意 e∈Ei， f（e）=i（i=1，2，…，
V（Fn）={vi i=0，1，…，n}， E（Fn）={v0vi i=1，2，…，n}∪{vivi+1 i=1，2，…，n-1} 记 n+1 阶轮 Wn 为
V（Wn）={vi i=0，1，…，n}， E（Wn）={v0vi i=1，2，…，n}∪{vivi+1 i=1，2，…，n-1}∪{v1vn}
— —— —— —— —— —— —— —— —— —— [收稿日期] 2008－04－23 [基金项目] 国家自然科学基金资助项目（10771091） [作者简介] 安常胜（1983-），男，甘肃榆中人，硕士研究生，研究方向：组合与网络优化的研究。
22
苏州科技学院学报（自然科学版）
2010 年
文中未加说明的符号或标记可见参考文献［2，8，9］。
≥3 i=4，5
C（v2′）={2，4，5} C（v3′）={3，4，5} C（w）={1，2，3}且|Ei|= 2 其他
显然，坌u，v∈V（M（C3）），若 u≠v，均有 C（u）≠C（v），且 |Ei|-|Ej| ≤1（i，j=1，2，3，4，5）。
所以，f 是 M（C3）的一个 5-VDEEC。
情形 1.2 当 n=4 时，令 C={1，2，3，4，5}构造 f 如下
f（v1v2）=f（v4v1′）=f（v4′w）=1 f（v2v3）=f（v1v2′）=f（v1′w）=2 f（v3v4）=f（v2v3′）=f（v2′w）=3
f（v1v4）=f（v3v4′）=f（v3′w）=4 f（v1v4′）=f（v4v3′）=f（v3v2′）=f（v2v1′）=5
λ λ max{min{λ|
λ i
≥ni}δ≤i≤△}为图 G 的组合度。
猜想 1[2，3] 对|V（G）|≥3 的简单连通图 G，则有 μ（G）≤χvde′（G）≤μ（G）+1。猜想 2[2，3] 对|V（G）|≥3 的简单连通图 G，则有 χvde′（G）=χvd′（G）。定义 3 对图 G（V，E），M（G）称为 G 的 Mycielski 图，如果 V（M（G））=V（G）∪V′∪{w}；
显然，坌u，v∈V（M（C4）），若 u≠v，均有 C（u）≠C（v），且 |Ei|-|Ej| ≤1（i，j=1，2，3，4，5）。
所以，f 是 M（C4）的一个 5-VDEEC。
情形 2 当 n≥5 时，可求得
λ λ λ λ λ λ μ（M（Cn））=max{min{λ|
λ n
≥1}，min{λ|
定理 1
4n
n
n=3
n
设
P（n）为
n
阶路（n≥2），则有
χvde′（M（Pn））=
5nn
n n
n=2，4 。
n
nnn
n
其他
证明情形 1 当 n=3 时，易得 μ（M（P3））=4。
显然，有 χvde′（M（P3））≥μ（M（P3））=4，只需证明 M（P3）有一个 4-VDEEC。
令 C={1，2，3，4}构造 f 如下
C（v1）={3，n} C（v1′）={1，3} C（v2）={2，3，4，n} C（vn）={1，2} C（vn′）={2，n} C（vn-1′）={1，2，n-1} C（vn-2）={1，n-1，n-2，n-3} C（vn-1）={1，2，n-2，n} C（vi）={i-1，i，i+1，i+2}（i=3，4，…，n-3}
理论和现实意义。目前，国内外众多学者对该问题作了大量工作，其中包括确定具有某种属性的特殊图的色
数的研究。笔者得到了圈、星的 Mycielski 图的点可区别均匀边色数。
定义 1[1~7] 对简单图 G 的正常边染色 f，任意 u,v∈V （G），若 C （u）≠C （v），其中 C （u）={f （uv） uv∈
C（vi′）={i，i+1，i+2}（i=1，2，…，n-2）且|Ei|=4（i=1，2，…，n）
显然，对坌u，v∈V（M（Cn）），若 u≠v，均有 C（u）≠C（v），且 |Ei|-|Ej| ≤1（i，j=1，2，…，n）。