几类图的L(j,k)-标号数

一些计算机无线网络的代码分配问题可以抽象为强乘积图和轮图的L(j,k)-标号问题(j≤k).针对强乘积图和轮图的L(j,k)-标号问题展开研究,确定了路与路,路与圈以及圈与圈之间的强乘积图的L(j,k)-标号数(这里j≤k≤2 j)和轮图的L(j,k)-标号数(这里j≤k≤2 j或k≥3j).     

路圈Cartesian积的局部替换图的L(1,1,1)-标号

图G的一个L(1,1,1)-标号就是从顶点集V(G)到非负整数集的一个映射f,使得当d(u,v)=1,2,3时,都有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中最大跨度f(v)的最小数为图G的L(1,1,1)-标号数,记为λ_1(G).给出了一类路圈Cartesian积的局部替换图的L(1,1,1)-标号数的确切值.     

点接拟梯子的L(d,1,1)-标号

图G的L(d,1,1)-标号指的是顶点集V(G)到非负整数集的一个映射f,且当d(u,v)=1时,|f(u)-f(v)|≥d;当d(u,v)=2时,|f(u)-f(v)|≥1;当d(u,v)=3时,|f(u)-f(v)|≥1。不妨假设最小的标号为0.G的L(d,1,1)-标号数λ(G)指的是G的全部L(d,1,1)-标号下的跨度max{f(v);v∈V(G)}最小值。基本上确定了点接拟梯子的L(d,1,1)-标号数。     

最大度是3的2-连通外平面图的(ρ,1)-全标号

图G的一个(ρ,1)-全标号是与频率分配有关的一种染色,它是从V(C)UE(G)到一个整教集合的映射,必须满足:(1)图G的任意两个相邻的顶点得到不同的整数;(2)图G的任意两个相邻的边得到不同的整数;(3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差ρ.一个(ρ,1)-全标号的跨度是指最大标号数与最小标号数的差.图G的所有(ρ,1)-全标号中最小的跨度,称为图G的(ρ,1)-全标号数.记为入TP(G).本文研究了最大度是3的2-连通外平面图G的全标号数.     

最大度是3的2-连通外平面图的（p，1）-全标号

图G的一个(p,1)-全标号是与频率分配有关的一种染色,它是从V(G)∪E(G)到一个整数集合的映射,必须满足:(1)图G的任意两个相邻的顶点得到不同的整数;(2)图G的任意两个相邻的边得到不同的整数;(3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差p.一个(p,1)-全标号的跨度是指最大标号数与最小标号数的差.图G的所有(p,1)-全标号中最小的跨度,称为图G的(p,1)-全标号数,记为λpT(G).本文研究了最大度是3的2-连通外平面图G的全标号数.     

图的最大度与（p,1）-全标号

图G的一个(p,1)全标号是与频道分配有关的一种染色,它是从V(G)UE(G)到一个整数集合的映射,且满足:1)图G的任意两个相邻的顶点得到不同的整数;2)图G的任意两个相邻的边得到不同的整数;3)图G的任意一个顶点和它所关联的边得到的整数必须至少相差P.一个(p,1)一全标号的跨度是指最大标号数与最小标号数的差.图G的所有(P,1)-全标号函数中最小的跨度,称为图G的(p,1)-全标号数,记为λTP(G).本文我们证明了对任意的图G,其最大度△是偶的且至少是10,则λT2≤2△-1.另外对于任意的简单连通图G,其最大度为△,如果G的最大度点的邻点中至多有△-1个最大度点,则λTP(G)≤p+4.     

图的邻域限制标号问题的性质

对于一个整数k>0,图G的一个k-L1,2-标号是一个映射c:V(G)→{0,1,2…k}且满足对任意的u,v∈V(G),若d(uv)=1,则|c(u)-c(v)|≥1且对任意的u,v∈v(G),若存在w∈V(G),使得u,v∈NG(w),则|c(u)-c(v)|≥2.则使得图G有一个k-L1,2-标号的最小的正整数k称为图G的邻域限制标号数,记为L1,2(G).本文主要给出了图G的邻域限制标号问题的几个性质.     

V_k~m-图的魔幻标号

证明了二部分Vm k-图是一个超级集有序π(-1)-边魔幻树当且仅当它是一个集有序优美树.给出了用具有超级集有序-边魔幻全标号二部分图来构造大的具有超级集有序-边魔幻全标号的图,得到了优美、超级集有序-边魔幻等标号的对偶标号以及关于超级集有序-边魔幻全标号的几个结果.     

基于F-图的标号算法

λ-魔幻标号空间和标号有序空间的定义使得分配无线电频道中互不干扰问题的解决有了理论依据。证明了利于研究广播标号(rolg)的F-图在一定的条件下,存在h∈Q_(λ-MLS)(G),并得到了其他研究rolg的图类可借鉴的快速大规模构造方法。可算法化的计算方法为实际应用提供了数理支撑。     

最大度为Δ图类的2-距离色数的一个下界

简单图G(V,E)的k-正常染色f称作G的k-2-距离染色,当且仅当(∨)w∈V(G),(∨)v,u∈N[w],满足f(u)≠f(v).得到了最大度为Δ的图类的2-距离色数的一个下界,χ2(Δ=d)≥{(d/2 1)2, d≡0(mod 2)(d 1)(d 3)/4, d≡1(mod 2)并回答了文献[1]提出的问题:能否找到一常数C,使得χ2(G)≤CΔ(G)对所有图G都成立.证明了这样的C是不存在的.