图的L(dm,1n)-标号

将图的L(d，1)．标号问题推广到L(d^m-，1^n-)-标号，并将其转化成该图的m-方图的L(d，1^n-)-标号．给出了求一般简单图的L(d，1^n-)-标号的两种算法．     

网格图的多重2-分离L(2,1)-标号

研究了两种网格图;正三角形,正六边形网格图。研究了它们的n重2-分离L(2,1)-标号以及n重2-分离L(2,1)-圆标号。用Kn表示n个点的完全图,图G的n重2-分离L(2,1)-标号就是复合图G[Kn]的L(2,1)-标号。通过对两种网格图的顶点循环地分配标号集,得到了正三角形网格的n重2-分离L(2,1)-标号数取值范围,并且完全确定了正六边形网格的n重2-分离L(2,1)-标号数。     

Mycielski图的L(2,1)-标号

设μ(G)表示一个图G的Mycielski图,λ(G)为G的L(2,1)-标号数.给出了λ(μ(G))的上、下界和λ(μ(G))达到下界(|G| 1)的一个充分条件.     

广义Petersen图的L(d,1)-标号

图G的顶点集到非负整数集的一个映射f满足：对任意的x,y∈V（G）,当dG（x,y）=1时,有｜f（x）-f（y）｜≥d;当dG（x,y）=2时,有｜f（x）-f（y）｜≥1。图的一个k—L（d,1）-标号是指图的一个标号L（d,1）使得min{f（v）｜v∈V（G）}=k,标号数简记为λd（G）。研究了广义的Petersen图的标号L（d,1）,给出一个特殊的标号方法,得到了广义的Petersen图的标号数λd（G）≤4d。     

双圈图的L（3,2,1）-标号

无向图G的L（3,2,1）-标号是指从顶点集V（G）到非负整数集Z＊的一个映射,满足：对i=1,2,3,只要d（x,y）=i,则｜f（x）-f（y）｜≥4-i。若一个L（3,2,1）-标号中的所有像元素都不超过整数k,则称之为图G的k-L（3,2,1）-标号。图G的L（3,2,1）-标号数,记作3λ（G）,是使得图G存在L（3,2,1）-标号的最小整数k。文中给出了双圈图和完全图的L（3,2,1）-标号数。     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

Halin图的L(d,l)标号

给定图G和正整数d,图G的L(d,1)标号是指从图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有|f(x)-f(y)|≥d;当dG(x,y)=2时,有|f(x)-f(y)|≥1。图G的L(d,1)标号数λd(G)是指最小的正整数k使得G有一个L(d,1)标号f满足f(V){0,1,2,…,k}。已知对于最大度为Δ的一般图有λd(G)≤Δ2 (d-1)Δ。讨论了Halin图的L(d,1)标号问题,证明了λd(G)≤Δ 3(2d-1)。     

一类广义Petersen图的L(2,1)-标号

图G的L(2,1)-标号是从图G的顶点集到非负整数集的一个映射f∶V(G)→{0,1,2,…},它满足对任意两个顶点x,y,当d(x,y)=1时,|f(x)-f(y)|≥2;当d(x,y)≥2时,|f(x)-f(y)≥1.研究了n≡0(mod3)的广义Petersen图G=P(n,t)的L(2,1)-标号数λ2,1(G),得到当t=0(mod3),5≤λ2,1(G)≤8,否则λ2,1(G)=5     

图的L(p,1T) 点标号问题

本文将距离为2的点的限制条件放松到支撑树上,提出了一类新的点标号问题,并相应给出了这种标号数的一般上界。     

关于n-格图及相关图的L(2,1)标号问题

图G的L(2，1)标号是一个从顶点集V(G)到非负整数集的函数?（x），使得若d(x，y)=1，则|?（x）-?(y)|≥2；若d(x，y)=2，则|?（x）-?(y)|≥1。移动通讯频率分配问题可转化为图的L(2，1)标号问题。将2-格图及相关图推广到n-格图及相关图，并给出了它们的L(2，1)标号。     

图的L(d,1,1)-标号

给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λ_d,1,1(G)≤Δ³-Δ²+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λ_d,1,1(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图： 拟正则树T_Δ及正则毛毛虫Cat_n, 给出了确切的L(d,1,1)-标号数, 其中d≥2.     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

一类连通可满着色图的L(2,1)标号

令G=(V(G),E(G))是一个简单图,Mp(G)为图G的广义Mycielski图.图G的L(2,1)标号数记作λ(G),定义为λ(G)=min{k|G有一个k-L(2,1)标号}.一个连续的L(2,1)标号是一个L(2,1)标号,使得所用的标号是连续的,相应的标号数记作-λ(G).凡是满足λ(G)=-λ(G)的图称为可满着色图.给出了一些特殊图的广义Mycielski图的L(2,1)标号数,从中发现一些广义Mycielski图为可满着色图,并由此猜想广义Mycielski图(除Mp(Kn)之外)为可满着色图.     

关于图的(d,1)-全标号

给出了星图、树图和均衡完全三部图的(d,1)-全数。     

拟m(o)bius梯子的L(2,1)-标号

图G的一个L(2,1)标号就是从顶点集V(G)到非负整数集的一个函数f,使得d(u,v)=1时,有|f(u)-f(v)| ≥2;当d(u,v)=2时,有|f(u)-f(v)|≥1,其中u,v是图G的顶点.不妨设最小标号为.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)标号下的跨度max {f(v);v∈V(G)}的最小数.本文定义了拟m(o)bius梯子,并完全确定了拟m(o)bius梯子的L(2,1)标号数.     

R（n，1×m）型图的L（3，2，1）-标号

文章给出了当n≤7时,R（n,1×m）型图的L（3,2,1）-标号数λ3,并提出当n≥8时,R（n,1×m）型图的L（3,2,1）-标号数λ3的猜想．     

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

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

外平面图的L(d,1)-标号

研究外平面图G的L（d,1）-标号问题,证明了外平面图的L（d,1）-标号数满足：Ad≤△＋2（2d—1）。对于L（d,1）-标号问题有一著名猜想：对最大度为△的任意图有A（G）≤△^2,本论文证明了此猜想对外平面图是正确的。     

关于图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G)|=k的L(2，1)-标号中的最小数k．将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了全图、块图的L(3，2，1)-标号数的上界．     

关于几类图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)|≥1．图G的三(2，1)-标号数λ(G)是使得G有max{f(v)：v∈V(G)}=k的L(2，1)-标号中的最小数k．该文将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了Kneser图、高度不正则图、Halin图的λ3(G)的上界．