论文部分内容阅读
随着图论理论的发展，图论分出许多分支，起源于150年前的四色猜想的染色问题有着极其重要的地位，并且在组合分析和实际生活中有着广泛的应用．染色问题是图论研究中一个很活跃的课题，得到了许多有趣而实用的结果，同时又拓展出一些新的分支．近年来，又提出了许多新的染色问题，这些染色问题在频率分配中有很强的应用，如：泛宽度染色，(p，1)—全标号．
定义1[1]设G=(V(G)，E(G))，d是一个正整数，X是V(G)的一个子集，如果X中任意两个顶点的距离都大子d，称X是一个宽度箱，d叫做X的宽度．显然，d—宽度箱也是(d-1)—宽度箱、(d—2)—宽度箱等等．
定义2[1]给定图G=(V(G)，E(G))，使得V(G)=X1∪X2∪…∪Xk(Xi(i=1，2，…，k)是V(G)的宽度两两不同的宽度箱)的最小整数k，这个整数k叫做图G的泛宽度色数，记做Xp(G)．图G的一个大小为Xp(G)的染色叫做Xp(G)—染色．显然，此处我们的目的是最小化k．可以假设对每个i，Xi是—个i—宽度箱．
图的泛宽度染色是一种以距离为依据准则的图顶点的剖分问题．对于不具有特定图结构的任意图来说，研究图的泛宽度色数是非常困难的，而且目前已知的结论中，也都是针对具有具体图结构的图类来研究的，如：无限正方形[2]，完全图Kn的剖分图S(Kn)[1]的泛宽度色数，无限3—正则树的泛宽度色数是7[3]．因此，在文献[1]中作者猜想：确定任意图的泛宽度色数是NP完备问题．
在频率分配问题中，会有下面的情形出现：我们需要给中转站分配频率波段(每个中转站得到对应于一个整数的频率波段)．为了避免干扰，如果两个站点离得非常近，那么它们的频率之差至少要相差2，而且，如果两个站点离得近(不是非常近)，那么它们得到的频率不同．受到这个问题的启发，Gringgs和Yeh[4]引进了L(2，1)—标号，它的自然推广是L(p，1)—标号，
定义3[5]设p是一个非负整数，图G的一个L(p，1)一标号是从V(G)到一个整数集合的映射L，必须满足：对于任意的顶点u，v
(1)若dG(u，v)=1，则|L(u)—L(v)|≥p；
(2)若dG(u，v)=2，则|L(u)—L(v)|≥1.
特别地，Whittlesey等人在文献[7]中研究了G的剖分图S1(G)的L(p，1)—标号，G的剖分图S1(G)是有图G在每条边上插入一个点所得到的图，S1(G)的L(p，1)—标号对应与G的L(p，1)—全标号．
定义4[5]设p是一个非负整数，图G的一个k—(p，1)—全标号是一个映射f：V(G)∪E(G)→{0，1，2，…，k}，使得：
(1)G的任意两个相邻的顶点u和v，有|f(u)—f(v)|≥1，
(2)G的任意两条相邻的边e和e，有|f(e)—f(e)|≥1，
(3)G的任意两个相关联的点v和边e，有|f(v)—f(e)|≥p，(p，1)—全标号的跨度是指两个标号差的最大值，图G的(p，1)—全标号的最小跨度叫图G的(p，1)—全标号数，记做λTp(G)．
[5]Fredeic Havet和Min—Li Yu给出了λTp(G)的上下界，提出了(p，1)—全标号猜想：λTp(G)≤△(G)+2p-1.在本文中，我们主要得到如下结论：
定义2.1[38]设G表示任意一个连通图，其中V(G)=．[v1，v2，…，vn}，G表示G的一个复制图，其中V(G’)={u1，u2，…，un)．在G和G之间加匹配viui(i=1，2，…，n)，得到新图D(G)，则V(D(G))=V(G)∪V(G)，E(D(G))=E(G)∪E(G)∪{viui，i=1，2，…，n}，不妨称D(G)为双图．
定理2.1设Pn表示一条阶为n的路，则当n＞5时，有xp(D(R))=5.
定理2.2设Wn表示一个轮，有Xp(D(Wn))=n+2.
定义3.1.1设G和G表示任意两个连通图，其顶点集分别为：在G和G，之间叠加匹配uivi，vivi+1，vivi+2，…，vivi+m，…，uivi+(n-1)(i=1，2，…，n；m=0，1，2，…，n-1；当i+m＞n时，i+m为模n意义下的加法)．这样得到一系列图G(1)n，n，G(2)n，n，…，G(m=1)n，n，…，G(n)n，n称为图G和G的弱联图．显然G(n)n，n：G∨G．
定理3.1.1设Pn表示一条阶为n的路，有λT2(Pn(m+1)n，n)：△+2：m+5(m=0，1，2，…，n．—2，n≥4)．
定理3.1.2设Cn表示一个圈，有λT2(Cn(m=+1n，n))≥△+2=m+5(m=0，1，2，…，n-1)；当n为偶数时，λT2(C(m+1)n，n)=△+2=m+5(m=0，1，2，…，n-1)．
定义3.2.1[29]设G是一个简单图，V(G)={v1，V2，…，Vn}．I2是两个点的独立集，G[I2]是通过I2代替G的每个顶点后所得到的图，即G的每个顶点vi都有一个复制点vi，I2中每个点仍按对应点的连边方式与其他点连边．G[I2]的点集和边集对应如下：则称G[I2]为G的点分裂图．
定理3.2.1 Pn表示阶为n的路，Pn[I2]表示路Pn的点分裂图，则有
定理3.2.2Cn(n≥3)表示一个圈，Cn[I2]表示圈Cn的点分裂图，则当n为偶数时，有λT2(Cn[I2])=6.
定理3.2.3 Kn[I2]表示完全图Kn的点分裂图，则有λT2(Kn[I2])≥2n．
定义3.3.1[12]设T(G)表示任意图G的全图，其顶点集对应于图G的顶点和边，全图T(G)中两个顶点是相邻的，当且仅当图G中对应的顶点或边相邻，或者是对应的顶点和边是相关联的，不妨设图G的顶点集V(G)={v1，v2，…，vn}，E(G)={e1，e2，…，em}，那么
E(T(G))={ViVj|vivj∈G}∪{eiej|ei和ej在G中相邻}∪{viej|vi和ej在G中相关联}．
定理3.3.1设T(Cn)表示圈Cn的全图，则有λT2(T(Gn))≥6；特别地，当n为偶数时，有λT2(T(Cn))=6.
定理3.3.2 Pn表示阶为n的路，T(Pn)表示路Pn的全图，则有
定理3.4.1设G表示一棵最大度△(G)=3的树，并且G中所有的最大度点在一条路上，则有λT2(G)≤5.
Fm表示阶为m+1的扇，当n个扇Fm的扇心连成圈时，用Cn·F[27]m表示．设则对于图Cn·F的(2，1)—全标号有下面的定理．定理3.4.2当n兰0(mod2)时，有
在含有n个顶点的路Pn上，当且仅当两点的距离(模)为k时加一条边，所得到的图称为pkn图[21][39]．下面我们给出了部分pkn图的(2，1)—全标号．
定理3.4.3对图pkn，有λT2(Pkn)=6，k＞1，n≥3k+2.
在含有n个顶点的圈Cn上，当且仅当两点的距离(模)为k时加一条边，所得到的图称为Chn图[22]，下面我们给出了图C24m(m≥1)的(2，1)—全标号．
定理3.4.4λT2(C24m)=6，m≥1.
对于完全图Kn，u，v∈V(Kn)，删去边uv，其它点和边不变，则得到了图Kn— uv，下面我们给出了一类图Kn— uv的(2，1)—全标号．
定理3.4.5当n为奇数且n≥3时，有λT2(Kn—uv)=n+1.
不妨设V(Cn)={v1，v2，…，vn}，V(Cn)的一个复制V(Cn)记为{u1，u2，…，un}，在V(Cn)和其复制V(Cn)之间叠加不同的匹配，就构成了一系列新图：Sn，Sn1，M(Cn)．下面我们给出了这些图的(，1)—全标号．
在V(Cn)和V(Cn)之间叠加匹配uivi(i=1，2，…，n)和vivi+1(i=1，2，…，n-1)，vnv1，得到图Sn，有：
定理3.5.1当n为偶数时，有λTp(Sn)=△+p=p+4.
在Sn(n为偶数)中，把Sn中所有ui(i=1，2，…，n)按u1u2，u2u3，…，un-1un，unu1的方式连成圈，得到图Sn1，有：定理3.5.2当n为偶数时，有λTp(Sn1)=△+p=p+4.
我们称由Mycielski作图法得到的图为Mycielski图，记为M(G)[31]．给定图G，顶点集V(G)={v1，v2，…，vn}，则图M(G)的顶点集和边集分别是：
定理3.5.3当n为偶数时，有n+p-1=△+p-1≤λTp(M(Cn))≤△+p+2=n+p+2.