APP下载

若干倍图的(2,1)-全标号

2012-10-25刘秀丽

延边大学学报(自然科学版) 2012年2期
关键词:定义研究

刘秀丽

(菏泽学院 数学系,山东 菏泽274015)

若干倍图的(2,1)-全标号

刘秀丽

(菏泽学院 数学系,山东 菏泽274015)

研究了与频道分配有关的一种(p,1)-全标号染色问题.根据倍图的构造特征,利用穷染法,给出了一种标号方法,得到了路、圈、星、扇的倍图的(2,1)-全标号数.(p,1)-全标号是对图的全染色的一种推广.

染色;(p,1)-全标号;(p,1)-全标号数;倍图

随着图的染色问题在现实中的广泛应用,它逐渐成为众多学者研究的重要领域之一.图的着色问题是图论中的重要研究分支,有很强的理论意义和实际意义.近年来,许多新的染色问题被提出,这些染色问题在频率分配中有很强的应用,如泛宽度染色、L(p,1)-标号[1-3]等.特别地,Whittlesey等人在文献[4]中研究了G的剖分图的L(2,1)-标号,G的剖分图S1(G)是由图G在每条边上插入1个点所得到的图.S1(G)的L(p,1)-标号对应于G的(p,1)-全标号.

图G为简单连通图,用V(G)、E(G)和Δ(G)分别表示图G的顶点集、边集和顶点的最大度.本文所讨论的图均为简单、有限图.

1 预备知识

定义1[5]设p是1个非负整数,图G的1个k-(p,1)-全标号是1个映射f∶V(G)∪E(G)→{0,1,…,k},使得:

当p=1时,图G的(p,1)-全标号对应于图G的全染色,因此,图的(p,1)-全标号也是对图的全染色的一种推广.本文主要讨论了若干倍图的(2,1)-全标号.

定义2[6]对简单图G,其顶点集为V(G)={u1,u2,…,un},图G′为G的拷贝,其顶点集V(G′)={v1,v2,…,vn},则称D(G)为G的倍图,其中:

引理1[5]对任意图G,有

引理2[7]若图G满足,映射f表示图G的1个标号集是{0,1,2,…,Δ(G)+1}的(2,1)-全标号,那么对图G的每个最大度点v,有f(v)=0或f(v)=Δ(G)+1.

引理3[5]若G是正则的,则λpT(G)≥Δ+p.

文中未加说明的记号和术语参见文献[8-9].

2 主要结果及证明

定理1 设Pn是阶为nn≥3的路……

登录APP查看全文

猜你喜欢

定义研究
FMS与YBT相关性的实证研究
2020年国内翻译研究述评
辽代千人邑研究述论
永远不要用“起点”定义自己
定义“风格”
视错觉在平面设计中的应用与研究
EMA伺服控制系统研究
新版C-NCAP侧面碰撞假人损伤研究
成功的定义
修辞学的重大定义