论文部分内容阅读
图理论是一门非常年轻的学科，但是成熟很快．它是一种能在各种科学领域像计算机科学，物理，生物，化学，战略学等学科中应用的模型．图染色问题是图研究中的主要领域之一．
频率分配问题(The Frequency Assignment Problem(FAP))是集中在点对点通讯问题中的一个一般的结构，例如无线电通信和移动电话网络．它要求用来传播的频率或频道之间的干扰保持在一个可接受的水平，进而有效地使用这些可用频率．在此问题中，我们需要给中转站分配频率波段．为了避免干扰，如果两个站点离得非常近，那么它们的频率至少要相差2.而且，如果两个站点离得近(不是非常近)，那么它们得到的频率不同．受到这个问题的启发，Griggs和Yeh[10]引入了L(2，1)—标号．2000年，G．J．Chang等人[11]把它推广到了L(p，1)—标号．图G的L(p，1)—标号是对G的顶点集的—个整数分配使得：若dG(u，v)=1，则|L(u)— L(v)|≥p；若dG(u，v)=2，则|L(u)— L(v)|≥1.
这个标号在一些文章中已经研究过了，[11]中研究了弦图，Whittesey等人在[12]中研究了G的剖分图的L(2，1)—标号．G的剖分图si(G)是由G的每条边上插入—个点所得到的图．s1(G)的L(p，1)—标号对应于在原图G上的(p，1)—全标号[13]：设p是一个非负整数，图G的一个k—(p，1)—全标号是一个映射f：V(G)U E(G)→{0，1，…，k}使得：
(1)G的任两个相邻的顶点u，v，有|f(u)—f(v)|≥1；
(2)G的任两条相邻的边e，e’，有|f(e)— f(e)|≥1；
(3)G的任两个关联的点u和边e，有|f(u)— f(e)|≥p．我们称这样的一个分配叫G的(p，1)—全标号．(p，1)—全标号的跨度是指两个标号差中的最大值．G的(p，1)—全标号的最小跨度叫(p，1)—全标号数，记作λTp(G)．它是一种加强了条件的全染色，这个额外的条件是关联的点和边的标号至少要相差p．
注意到(1，1)—全标号就是全染色，有λT1=XT-1，其中XT是全色数．
在文献[22]中给出了下述定义：
定义1[22]G=(V(G)，E(G))，d是一个正整数，X是V(G)的—个子集，如果X中任意两个点的距离都大于d，则称X是d—宽度箱，d叫做X的宽度．显然，d—宽度箱也是(d-1)—宽度箱，(d—2)—宽度箱等等．
定义2[22]给定图G=(V(G)，E(G))，使得V(G)=k∪i=1Xi，且Xi(i=1…k)是V(G)的宽度两两不同的i—宽度箱的最小整数k叫图G的泛宽度色数，记作Xp(G)．图G的一个大小为Xp(G)的染色叫Xp(G)—染色．显然，此处我们的目的是最小化k，可以假设对每个i，Xi是一个i—宽度箱，
泛宽度染色要求把所有的顶点剖分成宽度两两不同的i—宽度箱Xi，即同一宽度箱Xi中任两点的距离大于i，Xi中的顶点要求使用同一种颜色．
本文我们得到了如下的结论；
定义2.1.1[26]B={B1，B2，…，Bn}是一个集族．我们称n个顶点的图X(B)=(V，E)为B的交图：V(X(B))={Vi|i=1，2，…，n)，E(X(B))={vivi|()i，j=1，2，…，n；Bi∩Bj≠φ．}．
设Zn={1，2，…，n}，其幂集为Z={Z1，Z2，…，Z2n|()i，Zi∈Zn}．我们考虑由集族Z=Z—φ构成的交图X(Z’)的(p，1)—全标号．
定理2.1.1交图X(Z)如上所述，则
定理2.1.2若Kn，m(m＞n≥1)为完全二部图，且△＞p，则(1)n=1，m≥2时，λTp(Kn，m)=m+p-1.(2)n≥2，m＞n时，(i)若满足m—≥2p-1，则λTp(Kn，m)=m+p-1.(ii)若满足m—n≥p且m—n＜2p-1，则λTp(Kn，m)=m+p．
引理2.2.1[20]若G满足λT2(G)=△(G)+1且f是一个(△(G)+1)—(2，1)—全标号：V(G)∪E(G)→{0，1，2，…，△(G)+1}，则每个最大度点v，有f(v)=0或f(v)=△(G)+1.
引理2.2.2若G满足λTp(G)=A(G)+p-1且f是一个(△(G)+p-1)—(p，1)—全标号：V(G)∪E(G)→{0，1，2，…，A(G)+p-1}，则每个最大度点v，有f(v)=0或f(v)=△(G)+p-1.
定理2.2.3△＞p，如果图G含有一个最大度点v相邻于至少d(v)—p+1个最大度点，且最大度点的生成子图不含三角形，那么λTp(G)≥△+p．
定义2.2.1 G为简单图，V(G)={v1，V2，…，Vn}，把m个G的顶点vjo∈G(jo∈{1，2，…，n})连成圈，所得到的新图，记为Cm·G(vjo)，简记为G*．Gi(i=1，2，…，m)为G的m个复制图，即新图G*的点集和边集为：
定理2.2.4 G的最大度为A(G)，且λTp(G)=△(G)+p-1，取vjo为G的任一最大度点，不妨记为V1，由定义2.2.1得到的新图记为Cm·G(v1)，简记为G*1.则
定理2.2.5取G满足：G的(p，1)—全标号数为0≤λTp(G)≤2p-1，设f是G一个(p，1)—全标号：f：V(G)UE(G)→[0，1，…，λTp(G)]，存在v0∈V(G)使得f(v0)=0，取vjo为v0，不妨记为v1，由定义2.2.1得到的图记为Cm·G(v1)，简记为G*2设G中与v1相邻的边的最大标号为p+α(1≤α≤λTp(G)—p)，则m为偶数时，m为奇数时，
定义2.2.2 T为树，|T|=m，V(T)=．{u1，V2，…，um}，且T中除叶子外，其余点所有点的度数相等，△(T)=△．设G是一个n阶图，V(G)={v1，V2，…，Vn}，若G的(p，1)—全标号数为λTp(G)，G中存在△(△≥2)个标号相同的点V1，V，…，V△，其标号设为α0(0≤α0≤λTp(G))，且与每个vi(i=1，2，…，△)相邻的所有边的标号均小于与其相邻的vi的标号．
作G的m个复制图G1，G2，…，Gm，用Gi(i=1，2，…，m)代替ui(i=1，2，…，m)，当Gi，Gj对应的T中的点ui，uj相邻时，把Gi中某个标号为α0的点与Gj中某个标号为α0的点连接起来，且Gi(i=1，2，…，m)中标号为α0的点只能与Cj(j≠i)中一个标号为α0的点相邻，G中其余点的连边方式不变．这样所得到的图记为T·G(v1，V2，…，v△)，简记为GT．
定理2.2.6GT如上所述，则λTp(G)≤λTp(GT)≤λTp(G)+2.
把定义2.2.2中的G的△个标号相同的点V1，V2，…，VA，其条件改为对()vi(i=12，…，△)，其邻边中至少有一条边e的标号大于与其相邻的vi的标号，与所有V1，v2，…，v△相邻的边中最大标号为p+α(0≤α≤λTp(G)—p)．
按照定义2.2.2中的构造方式构造新图，这样所得到的图记为T—G(v1，V2，…，v△)，简记为G"T．
定义2.3.1[25，51]对两个图G和H，笛卡尔乘积图G□H定义如下：V(G□H)=V(G)×V(H)；E(G□H)={(u，v)(u’v)|v=v且uu∈E(G)或u=u’且vv∈E(H)}．
定理2.3.1 Pm为长为m的路，V(Pm)={u1，u2，…，um，um+1}．H满足；|H|=n，V(H)={v1，V2，…，Vn)，H的(p，1)—全标号数为λTp(H)，且存在点v，其邻边中至少有一条边的标号大于v的标号，设所有边中的最大标号为p+α(α≥0)，作Pm与H的笛卡尔积Pm□H，V(Pm□H)={(ui，vj)|i=1，2，…，m+1；j=1，2，…，n)}
定义3.1.1[51]G是一个简单图，V(G)=．[v1，V2，…，vn}，I2是两个点的独立集，G[I2]是用I2代替G的每个顶点所得到的图．G[I2]的点集和边集如下：V(G[I2])={v1，v2，…，vn，v1，v2，…，Vn}，E(G[I2])=E(G)∪{vivj，vivj|vivj∈E(G)}．G[I2]称为G的点分裂图．
定义3.2.1[36]给定m个图G0，G1，…，Gm-1，对i=0，1，…，m-1，令ei=vivi+1∈Gi，令cm=c0c1…Cm-1为长是m的圈，构造新图：
(1)删去ei，i=0，1，…，m-1.
(2)合并所有的vi成—个点x．
(3)将vi+1与ci合成—个点，i=0，1，…，m-1(i+1取模m)．令此图为S1(G0，e0，G1，e1，…，Gm-1，em-1)，简记为S1.
若给定m个图Kmo，i=1，2，…，m，则S1(G0，e0，G1，e1，…，Gm-1，em-1)=S1(Kn1，e1，Kn2，e2，…，Knm，em)，简记为S2.记所有的vi合并成的点为x为v0，Vi+1与ci合并成的点依次记为v1，v2，…，vm； vi对应的Lni中的其余的点分别记为vi1，vi2，…，vi(ni—2)，i=1，2，…，m．
定理3.2.1S2如上所述，则Xp(S2)=[m/2]+1+m∑i=1(ni—2)．