图的L(d,1)-标号的一个推广

引入裂变图的概念，将图的L(d，1)-标号推广到赋权图的L（0,1,2,d,d,1)-标号，给出了一般图的裂变图的L（0，1，2，d,d,1)-标号数的一个上界，并分别给出了两类平面图及相关图的裂变图L（0,1,2,d,d,1)-标号数一个上界。     

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

给出了星图、树图和均衡完全三部图的(d,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)。     

广义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。     

一类广义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     

无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.     

毛毛虫树的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)标号数.     

图的一种特殊的(d,1)-全标号

设图G是有限的、无向的简单图.对于△(G)≥2d+2的情况,给出了一种在[0,2△+d-2]上d-好标号的方法,改进了相关文献的结果.     

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

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

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

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

无爪图与分裂图的L(d,1)-T标号

给定一个简单连通图G及其一棵支撑树T,图G的1个L(d,1)-T标号即一个标号函数g满足:①G的任意2个相邻点的标号至少差1;②T上任意两个相邻点的标号至少差d;③G上任意两个距离为2的点的标号至少差1.本文研究了无爪图与分裂图的L(d,1)-T标号并给出了Tld,T(G)一个界.     

简单图的L(2,1,1)-标号

给出了完全图、完全二分图、路、圈等简单图的L(2,1,1)-标号数。对最大度为Δ 的一般图G,给出了构造L(2,1,1)-标号的一个算法, 证明了λ_2,1,1(G)≤Δ³- Δ²+2Δ。     

最大度至多为4的平面图的L(p,q)-标号

利用欧拉公式和权转移规则,证明了:若G为不含4,5,6-圈和2个相交三角形且满足Δ(G)≤4的平面图,则L(p,q)-标号数的上界为(2q-1)Δ(G)+6p+2q-4.     

关于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(p,q)-标号

对于正整数p,q,n与图G,如果函数φ:V(G)→｛0,1,2, ,n｝满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4.