论文部分内容阅读
图的染色问题是图论中研究的主要问题之一,也是图论研究中一个活跃的领域,因此各类染色问题被相继提出并加以发展应用,其中图的染色问题的一个重要推广是图的标号问题.作为频道分配问题的一个变形，Griggs和Yeh在1992年文章[1]中提出了图的L(2,1)-标号问题.假如给定一些基站,我们想给每一个基站在避免干扰的条件下给它分配一个频道.为了避免干扰,我们要求非常近的基站之间必须是至少差两个频道的,稍近的一些基站也让它们分配不同的频道.为了方便起见,把基站看作是点,如果两个基站非常近则在两个基站间连一条边,如果两个点距离为2则对应的基站可以看作是稍近.这样我们就可以定义L(2,1)-标号了本文只考虑简单连通图G.定义1图G的一个L(2,1)-标号是一个满足下面两个条件的映射c：V(G)→(0,1,2…k},(1)对任意的u,v∈V(G),若d(u,v)=1,则|c(u)-c(v)|≥2；(2)对任意的u,v∈V(G),若d(u,v)=2,则|c(u)-c(v)|≥1.当所有的标号都小于等于k时,则称图G有一个k-L(2,1)-标号.使得图G有一个k-L(2,1)-标号的最小的正整数k称为图G的L(2,1)-标号数,记为λ(G).同样的,我们可以定义L(d,1)-标号.定义2图G的一个L(d,1)-标号是一个满足下面两个条件的映射c：V(G)→{0,1,2…k},(1)对任意的u,v∈V(G),若d(u,v)=1,则|c(u)-c(v)|≥d；(2)对任意的u,v∈V(G),若d(u,v)=2,则|c(u)-c(v)|≥1.当所有的标号都小于等于k时,称图G有一个k-L(d,1)-标号.使得图G有一个k-L(d,1)-标号的最小的正整数k称为图G的L(d,1)-标号数,记为λd(G).记λ2(G)=A(G).现在已经有很多的文章在研究L(2,1)-标号问题,但是很多文章是在特殊图类上研究λ(G).Griggs和Yeh[1]证明了对最大度是△的一般图G,λ(G)≤△2+2△. Chang和Kuo[2]把上界改进到△2+△,近期Kral和Skrekovski[3]把上界改进到了△2+△-1,并证明了若图G的直径是2,则λ(G)≤△2,指出了Moore图是可以达到这个上界的.因此Griggs和Yeh[1]猜想对任意的△≥2的图G最好的上界是△2,且证明了确定图G的λ(G)是NP-困难的.本文中△(G)表示图G的最大度,δ(G)表示图G的最小度,d(u,v)表示u,v两点在图G中的距离,即u,v之间最短路的长度.在本文的第二章中,我们研究了图G的(d,1)-全标号.Whittleseyet等人在文章[4]中研究了图G的第一剖分图的L(d,1)-标号.图G的第一剖分图s1(G)是图G通过在每一条边上加一个点得到的.图G的第一剖分图s1(G)的L(d,1)-标号其实就是图G的(d,1)-全标号.定义3[5]图G的(d,1)-全标号是满足下面三个条件的映射c：V(G)∪E(G)→{0,1,2…k},(1).对任意的u,v∈V(G),若uv∈E(G),则c(u)≠c(v)；(2).对任意的u,v,w∈V(G),若uv,uw∈E(G),则c(uv)≠c(uw)；(3).对任意的u,v∈V(G),若uv∈E(G),则|c(u)-c(uv)|≥d.我们把这种映射称为图G的(d,1)-全标号.一个(d,1)-全标号的跨度是指最大标号数与最小标号数的差,图G的所有(d,1)-全标号中最小的跨度,称为图G的(d,1)-全标号数,记为λdT(G).对于最大度为△的一个图G,图G在[0,q]上的一个(d,1)-全标号如果满足,对于任意的点v∈V(G),其标号均在[0,△+d-1]内,则称此标号为一个d-优(d-good)标号,设p是图G的点集V(G)的一个剖分, V(G)=A∪B,A∪B=φ,其中边集E(G)＼(E(A)∪E(B))称为G的割,记为[A,B].图G的一个割边数目最多的割称为图G的最大割.目前,在文章[5]中对任意图G,猜想λdT(G)≤△+2d-1.这就是著名的全标号猜想.并且在[8]中证明了对任意的图G,λdT(G)≤2△+d-1,λ2T(G)≤6若△(G)≤3,λ2T(G)≤8若△(G)≤4.下面我们给出第二章的两个主要结论.定理2.5对任意的简单图G,最大度为Δ,如果Δ是偶的且Δ≥10,则λ2T(G)≤2Δ-1.定理2.6设图G是一个连通图且最大度为Δ,如果Δ(G)≤3且最大度点的邻点中至多有Δ-1个最大度点,则λdT(G)≤d+4.Hajo Broersma[6]曾经把古典的顶点标号进行变形,提出了图的干道限制染色(Backbone-染色).即把原来图G上的限制只在图G的某一个主干道上加强.受此启示,本文在第三章中所要研究的L(d,1)-T标号是比L(d,1)-标号要求更松的一种限制.还是要求相邻的以及距离为2的基站频道必须不同,另外要求在图G的任意一棵支撑树T上相邻的基站频道至少差d.也就是只在图G的某个重要的干 道上我们要求的严格一些.这里我们以支撑树作为主要枢纽.对于任意连通图G,都有支撑树.所以我们引入以下定义：定义4给定一个简单连通图G及其一棵支撑树T,图G的一个L(d,1)-T标号是一个满足下面三个条件的映射c：V(G)→{0,1,2…k},(1)对任意的u,v∈V(G),若d(u,v)=1,则|c(u)-c(v)|≥1；(2)对任意的u,v∈V(G),若dT(u,v)=1,则|c(u)-c(v)|≥d；(3)对任意的u,v∈V(G),若dG(u,v)=2,则|c(u)-c(v)|≥1.当所有的标号都小于等于k时,则称图G有一个k-L(d,1)-T标号.使得图G有一个k-L(d,1)-T标号的最小的正整数k称为图G的L(d,1)-T标号数,记为λd,T(G).我们定义Tλd,T(G)：=maxT{λd,T(G)：G是一个图且T是图G的一棵支撑树}.若图G不含K1,3,则称图G是无爪图.设V(K1,n)={v0,v1,v2,…,vn}且Δ(v0)=n,则称v0为K1,n的一个控制点.设图G是一个简单图, V(G)={v1,v2,…,vn},G[I2]的点集和边集如下定义：V(G[I2])={v1,v2,…,vn,v’1,v’2,…,v’n},E(G[I2])=E(G)∪{v’iv’j,v’ivj,viv’j|vivj∈E(G)},则G[I2]称为G的点分裂图[7].在本文的第三章我们主要得到了以下结论.定理3.1.1对于任意的简单连通图G,其最大度为△,则Tλd,T(G)≤△2+2d-2.定理3.1.2设G是一个简单连通图,最大度为△,且图G的最大度点的邻点中至多有△-1个最大度点,则Tλd,T(G)≤△2+2d-3.引理3.1.3若图G是至少有一条边的简单图,则limd→∞(λd+1(G))/(λd(G))=1.定理3.1.4如果G是一个简单连通图,则limd→∞(Tλd+1,T(G))/(Tλ(?)(G))=1.定理3.2.2设G是无爪的连通图,则Tλd,T(G)≤3/4△2+2d+1/2△-2.定理3.2.3若G’为连通图G的点分裂图,△(G)=△,则Tλd,T(G’)≤2△2+2d+△-2.在本文第四章中研究的L’(d,1)-T标号是比L(d,1)-T标号要求更松的一种限制.还是要求相邻的基站频道必须不同,另外要求在图G的任意一棵支撑树T上相邻的基站频道至少差d且在T上距离为2的基站频道至少差1.也就是只在G的某个重要的干道上我们要求的严格一些.这里仍以支撑树作为主要枢纽.我们引入以下定义：定义5给定一个简单连通图G及其一棵支撑树T,图G的一个L’(d,1)-T标号是一个满足下面三个条件的映射c：V(G)→{0,1,2…k},(1)对任意的u,v∈V(G),若d(u,v)=1,则|c(u)-c(v)|≥1；(2)对任意的u,v∈V(G),若dT(u,v)=1,则|c(u)-c(v)|≥d；(3)对任意的u,v∈V(G),若dT(u,v)=2,则|c(u)-c(v)|≥1.当所有的标号都小于等于k时,称图G有一个k-三L’(d,1)-T标号.则使得图G有一个k-L’(d,1)-T标号的最小的正整数k称为图G的L’(d,1)-T标号数,记为λ’d,T(G).我们定义Tλ’d,T(G):=maxT{λ’d,T(G):G是一个图且T是图G的一棵支撑树}.在本文的第四章中我们给出了以下主要结论.定理4.1.1对于任意的简单连通图G,其最大度为△,则Tλ’d,T(G)≤2△+2d-3.定理4.1.2设G是一个简单连通图,最大度为△,且图G的最大度点的邻点中至多有△-2个最大度点,则Tλ’d,T(G)≤2△+2d-4.定理4.2.1对任意的简单连通图G,其最大度为△,则图G存在一棵支撑树T0,使得λ′d,T0(G)≤2△+2d-4.定理4.2.2如果G是一个简单连通图,则limd→∞(?)=1.定理4.2.3若G’为连通图G的点分裂图,△(G)=△,则G’存在一棵支撑树T0,使得λ’d,T0(G’)≤3△+2d-2.