两类图的点可区别边染色数.pdfVIP

山西大学学报(自然科学版)35(1)：24～26，2012 of Shan】【i Journal University(Nat．Sci．Ed．) 文章编号：0253—2395(2012)01—0024—03 两类图的点可区别边染色数 唐保祥1，任韩2 (1．天水师范学院数学与统计学院，甘肃天水741001；2．华东师范大学数学系，上海200062) 摘 要：证明了．任意正整数k≥2，存在点可区别边色数为2k+1的k+1一正则图；任意正整数m≥4。存在点可 区别边色数为m的偶图． 关键词：正则图；偶图；点可区别边染色；点可区别边色数 中图分类号：0157．5 文献标识码：A 0 引言 图的点可区别边染色问题具有广泛的应用背景和重要理论意义，是图论研究的重要课题之一，也是当前 活跃的前沿学科问题．目前，图的点可区别边染色理论提出了一些新概念和新猜想，得到了一系列有意义的 新结果[卜16]． 本文讨论的图均是有限简单无向标号图(即顶点间是有区别的)． 定义1[17]设G是一个简单图，k是正整数，厂是从E(G)到{1，2，…，k)的一个映射，对任意两条相邻边 G的k— PEC}为图G的边色数． 定义2[卜33 U，口∈y(G)，当“≠口时，总有C(“)≠ 对简单图G(V，E)，f是图G的七一正常边染色，若V ofG，称 Z7td(G)一min{kIk-VDECG)为图G的点可区别边色数． of 定义3[卜21对简单图G，rli表示度为i的顶点的个数，艿，△分别表示图G的最小度和最大度，．￡l(G)= ，1、 max{min{AIf^1≥”。}}称为图G的组合度． 参≤，≤△ 、l I 猜想‘卜31对Iy(G)I≥3的连通图G，la(G)≤X7耐(G)≤产(G)+1． 1结果及其证明 定理1 对任意正整数k，存在具有户个顶点q条边，点．--／区别边色数为2k+1的k+1一正则图 G。c阳蜞中户一(：笔1)旷虿1·(川2k+1)Ⅲ㈨． 证明 l ∈E(Gt)当且仅当 {q。p“。 1≤i·iz…厶+I≤竹}，可t。p“，qm…j。 V(G,)令溉矗， …一：，…^+l}呐，瘟．…以+l}l_1．由G。定义知|邶。)l=(：甚1)．V吣‰。E …，J。}=N一{iI，i。，…，iI+l}，V 收稿日期：201l—03—29；修回日期：2011-06一13 作者简介：唐保祥(1961一)，男。甘肃天水人，副教授．研究领域：图论和组合数学．E-mail：tbx0618@sina．eom 万方数据 唐保祥等：两类图的点可区别边染色数 25 E(G1)I “+l，则Vili2．．．‘+。弘112一川∈E(G1)，所以顶点u…。叫。的度为d(口叫。…i．+。)；惫+1·因此I2言‘ V(G。)I，口=I (i：1)·(点+1)．令户=I 下。 V奶Ii2…。+，功。』：…』川E 色t，eP，(V小：…‘+。功。如…』…)一f，显然1≤￡≤2志+1． Vuflf2…‘+IV(G1)·若Uilf2…‘+Iq1 u，1r2…飞+I∈E(G1)’功1 r2…，+l·且