资源描述：
《halin图的l（d，1）标号》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Halin图的L（d，1）标号第19卷第1期2006年3月青岛大学(自然科学版)vO1.19No.1JOURNALOFQINGDAOUNIVERSITY(NaturalScienceEdition)Mar.2006文章编号:1006—1037(2006)01—0021—03Halin图的L(d,1)标号张苏梅,王纪辉,马巧灵(济南大学理学院,山东济南250022)摘要:给定图G和正整数d,图G的L(,1)标号是指从图G的顶点集到非负整数集的一个映射厂满足:对任意的,∈,/r(G),当如(,)一1时,有l厂()一厂()l≥;当dG(,)一2时,有l
2、厂()一厂()l≥1.图G的L(,1)标号数(G)是指最小的正整数是使得G有一个L(,1)标号厂满足厂(,/r){0,1,2,…,是).已知对于最大度为△的一般图有(G)≤A.+(一1)A.讨论了Halin图的L(d,1)标号问题,证明了(G)≤A+3(2d一1).关键词:Halin图;L(d,1)标号;L(d,1)标号数中图分类号:O157.5文献标识码:A1图的L(d,1)一标号设图G的点集和边集分别用,/r(G)和E(G)表示.对任意的∈,/r(G)用dc()表示G中顶点的度数;分别用△和表示图G的最大度和最小度.对任意的,∈,/r(G),
3、dc(,)表示顶点,之间的距离.其它未定义的符号见[1].RobertsE.]把频率分配问题归结为图的一个标号问题.定义1.1设Z为非负整数集合,f:(G)一Z为一个映射,若对任意的,∈,/r(G),满足当如(,)一1时,有l厂()一厂()l≥2;当do(x,)一2时,有l厂()一厂()l≥1,则称厂为G的一个L(2,1)标号.图的一个是一L(2,1)标号是指图的一个L(2,1)标号使得所有标号都不超过是并且至少有一个点的标号为是.我们称使G有一个是一L(2,1)标号的最小是值为图G的L(2,1)一标号数,记为(G).Griggs和YehE.]确
4、定了A(P),()和(w)的具体数值,其中P是72个顶点的路,是72个顶点的圈,w是C加上一个与C中所有顶点都相邻的顶点得到的图称为一轮.对最大度为△的树T,Griggs和YehE.]证明了(T)为△+1或△+2.他们还证明了一般图的L(2,1)标号问题是NP一完备的,而且对最大度为△≥1的图G,(G)≤△.+2A,当G为3一连通图时,上界改进为(G)≤A.+2A一3,当G是直径为2的图时,上界改进为(G)≤A..于是Griggs和Yeh_3]还猜想对任何最大度为△的图,总有(G)≤A..GJChang和DavidKuo[4]又把一般图的L(2,
5、1)标号数的上界改进为(G)≤△.+△,但离证明Griggs和Yeh的猜想(G)≤A.还有很大的差距.要直接证明Griggs和Yeh的猜想比较困难.目前,关于图的L(2,1)标号问题的研究大都集中在证明该猜想对某些特殊图成立.定义1.2给定图G和正整数d,图G的L(,1)标号是指从图G的顶点集到非负整数集的一个映射.厂满足:对任意的,∈,/r(G),当dG(,)一1时,有l厂()一厂()l≥;当dG(,)一2时,有l厂()一厂()l≥1.图G的L(,1)一标号数(G)是指最小的正整数是,使得G有一个L(,1)标号厂满足厂(,/r){0,1,2,…
6、,是).作为L(2,1)标号问题的推广L(d,1)标号问题同样也是NP一完备的.Chang等_5]研究了一般图的收稿日期:2005—12—16;修回日期:2006—02—28基金项目:山东省自然科学基金资助项目(Y20O3A_O1)作者简介:张苏梅(1961一),女,江苏南通人,副教授,主要从事图论及其应用方面的研究.22青岛大学(自然科学版)第l9卷L(d,1)标号问题,证明了任意一般图的L(d,1)标号数d(G)满足d(G)≤A-t-(一1)LX.本文主要讨论了halin图的L(d,1)一标号问题,并证明L(d,1)一标号数d(G)≤A-t-
7、3(2d—1).显然,当d一2时有halin图的L(2,1)一标号数(G)≤A+9.2Halin图的定义及性质Halin图是一类特殊的平面图.张忠辅等嘲研究了Halin图的染色问题,并讨论了Halin图的一些结构性质.下面给出Halin图的定义和性质.定义2.1E.]设图G是3一连通平面图,是G的外部面,如果(G)≥3,且G去掉,.的边界之后是一棵树,则称G为Halin图.为方便讨论,称除了的其它面为内部面,在上的点为外点,其它点为内点.轮图是恰好有唯一内点的一类特殊的Halin图.引理2.1E]设G是Halin图,对任意的EV(fo),则()一
8、3(V(fo)表示面,O上的点集)引理2.2_6]设G是Halin图且不是轮图,则在G中必存在一个内点叫与唯一的内点相邻,即可设N(叫)
