拟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)标号数.     

拟梯子的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的顶点.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v ∈ V(G)}的最小数.本文定义了拟梯子,并完全确定了拟梯子的L(2,1)-标号数.     

点接拟梯子的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.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v∈V(G)}的最小值.定义了点接拟梯子,并完全确定了点接拟梯子的L(2,1)-标号数.     

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

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

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

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

点接拟梯子的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)-标号数.     

拟Mobius梯子的L(1,1,1)-标号

图G的一个L(1,1,1)-标号是从顶点集V(G)到非负整数集的一个映射f,且当距离d(u,v)=1,2,3时,均有|f(u)-f(v)|≥1;其中,u,v是图G的顶点.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中的最大跨度的f(v)最小数为图G的L(1,1,1)-标号数,记为λ_(1,1,1)(G).给出了拟Mobius梯子的L(1,1,1)-标号数的确切值或上下界.     

关于图的L（d1，d2，d3）-标号问题

图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)-标号数λ(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)-标号中的最小数k.本文将L(2,1)-标号问题推广到更一般的情形即L(d1,d2,d3)一标号问题.并得出了一般图和平面图的λd1,d2,d3(G)的上界.     

毛毛虫树的L(3,2,1)-标号问题

图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z^*的一个映射f,满足：对于任意两个不同顶点u和v,若d(u,v)=i(i=1,2,3),则|f(u)-f(v)|≥4-i.若图G的一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为图G的k-L(3,2,1)-标号.图G的L(3,2,1)标号数,记作λ_3,2,1(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.本文确定了完全最大度不小于4的毛毛虫树的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)的上界．     

一类广义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(1, 1, 1)-标号

一个图G的L(1, 1, 1)-标号是指从顶点集V(G)到非负整数集的一个映射f,且使得:当两顶点距离d(u,v)为1、2或3时,|f(u)-f(v)|≥1。假设最小的标号为0,称L(1, 1, 1)-标号中使用的最大标号为该标号的跨度。图G的L(1, 1, 1)-标号数λ(G)是G的所有L(1, 1, 1)-标号下的跨度max﹛f(v);v∈V(G)﹜的最小值。研究了点接拟梯子的L(1, 1, 1)-标号,通过顶点分组和循环标号,完全确定了点接拟梯子的L(1, 1, 1)-标号数。     

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)。     

两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.     

平面三角剖分图的L(2,1)标号

图G的L（2，1）标号是从一个顶点集V（G）到非负整数集的函数f(x)，使得若d(x,y)＝１，则|f(x)-f(y)|≥２；若d(x,y)=2，则|f(x)-f(y)|≥1。图G的L（2，1）标号数λ（G）是使得G有max{f(v):v∈V（G）}=k的L（2，1）标号中的最小数k。本文证明了对最大度数为△的一般平面三角剖分图G，有λ（G）≤△^2-△；当G的直径大于2时，有λ（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(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)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 ,有上述猜想成立     

拟mbius梯子的(1,1)-全标号

图的(1,1)-全标号是从点集及边集到非负整数集的一个函数f,且满足:任两相邻顶点标号相异;任两相邻边标号相异;及任关联的点和边标号也相异.本文对拟mbius梯子的(1,1)-全标号进行研究,确定了拟mbius梯子的(1,1)-全标号数.     

一类连通可满着色图的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)之外)为可满着色图.     

手镯图的L(2,1)—标号

为了更好地研究频道分配问题,引入了从顶点集到非负整数集的一个函数,即图的一个L(2,1)—标号。假设最小标号为零,图的L(2,1)—标号数就是此图的所有L(2,1)—标号下的跨度的最小数。对于路和圈[WT]的Cartesian积图的推广图——手镯图的标号数问题,给出了手镯图的定义,即是将拟梯子的两端重合而得到的图形,同时给出了其L(2,1)—标号数的定义,运用顶点分组标号法,根据圈的个数和每个圈的顶点数的不同进行分类讨论,研究结果完全确定了手镯图的L(2,1)—标号数的确切值,丰富了图的种类并完善了标号数理论。