资源描述：
《点可区别边色数的一个上界》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、点可区别边色数的一个上界第22卷第1期2008年1月甘肃联合大学(自然科学版)JournalofGansuLianheUniversity(NaturalSciences)Vo1.22No.1Jan.2008文章编号:1672—691X(2008)01—0004—03点可区别边色数的一个上界安明强(天津科技大学理学院,天津300457)摘要:设G是简单图,,是从V(G)UE(G)到{1,2,…,k}的一个映射.对每个U∈V(G),令C(")={f(uv)l∈V(G),UV∈E(G)}.如果是k一正常边染色,且对任意U,∈V(
2、G),有C(")≠C(),那么称为图G的点可区别边染色(简称为k-VDEC).数x(G):min{klG有k-VDEC)称为图G的点可区别边色数本文通过应用概率方法,证明了对任意最大度△≥2的图G,x(G)≤16△.关键词:边染色;点可区别边染色;点可区别边色数;一般局部引理中图分类号:Ol57.5文献标识码:A本文所考虑的图均为连通的,限的,无向的简单图.定义1E,设G是阶数至少为2的简单连通图,足是正整数,若/是从V(G)UE(G)到{l,2,…,七)的一个映射,使V",lAW∈E(G)(≠),f(uv)≠厂(uvJ);
3、V",∈V(G),C(")≠C(),或C(")≠C(),其中C(u)={/(WU)l∈V(G),"∈E(G)},(")一{l,2,…,k}一c("),则f称为是G的一个七一点可区别边染色,简记为k-VDEC.称rainf启!G存在七一VDEC)为G的点可区别边色数(或强边色数),记为x(G)或obs(G).显然,一个图G具有点可区别边染色当且仅当G是没有孤立边,且最多有一个孤立点的图.这样的图称为VDEC图.设G是一个VDEC图,(G)表示G的k度顶点个数.令(G)一rain{Z{()≥(G),≤k≤△},(G)称为图G的组
4、合度.显然X(G)≥(G).猜想1I2设G是VDEC图,(G)为G的组合度,则x(G)一(G),或者x(G)一(G)十1.文[1_3]分别研究了图的点可区别的边染色问题,得到了一系列好的结果.Hatami在文[4]中确定了图的邻点可区别边色数的上界为△+300.但是,要确定图的点可区别边色数的上界,一直是很困难的问题.引理1](一般局部引理)考虑(典型的坏的)事件的集合e一{A,A!,…,A},对每一个A,,都存在D,(D可以空),使得每一个A,与e一(DUA)互相独立(对某个D￡).如果有实数z,z,…,z∈[O,1)使得
5、对每个1≤i≤,P,(Ai)≤zi-I(1一z,),则￡中所有事件都不发生A,∈D的概率至少是Ⅱ(1一z)>O.=1本文通过尝试应用一般局部引理,得到了最大度△≥2的任意图的点可区别边色数的上界为l6△.文中未加述及的术语和符号可参见文[6].定理1对任一最大度为△的图G,△≥2,有x(G)≤16△.证明令△一,f:E一{l,2,…,16d)表示G的边的随机染色,并对任意∈E(G),厂(P)是从{1,2,…,16d}中随机地均匀地选择的.为了保证点可区别的边染色,需满足以下两个条件:(A)正常边染色——没有两条相邻的边
6、染成同一种颜色.(B)点可区别——没有任何两个顶点关联同样的颜色集合.为此,定义如下坏事件:(I)对每一对相邻的边A一{,.},令表示和:被染成同种颜色的事件.(II)对任意两点",∈V(G),如果C()一C(),令表示C(")一c()的事件.注意到如果(I)和(II)都不发生,则厂是G的点可区别的边染色.为了运用引理1,需进行以下几步:(1)计算坏事件发生的概率:收稿日期:2007—10—20.作者简介:安明强(1982一),男,甘肃天水人,天津科技大学助教,硕士,主要从事图论及其应用的研究笫1期安明强:点可区别边色数的一
7、个上界5Pr()一,P.(ER…)=渤≤?(2)计算相关事件数.构造相关图H,H中的结点就是两种类型的所有事件,其中两个结点Ex和E(X和y要么表示一对关联的边,要么表示一条边的双星图)相邻当且仅当X和y含一条公共边,因为每个事件E的存在仅依赖于X的边.由相关图的构造可得,每一个事件与至多4d--5个相关(因为和一条边e相交的边数至多是2d--2(除去e本身),事件EA中包含两条边e.和e.,所以分别和e.,e相交的边数至多是2(2d--2)一4d--4,又因为和e.相交的边中有e,和.相交的边中有e.,所以A一{e,e)被
8、计算了两遍,应减1),与至多4d个Ee…相关(和一条边相交的边数至多有2d,而事件包含有两条边).每一个事件EB…与至多2d(2d--2)-~EA相关(因为和一条边e相交的边数至多是2d--2(除去e本身),事件玩.中至多包含2d条边),与至多4d个Ee…相关(原因如前).(3)构造常数?
