几类轮图构造图的(2,1)-全标号

研究了与频道分配有关的一种染色问题——(p,1)-全标号。(p,1)-全标号是从V(G)∪E(G)到集合{0,1,…,k}的一个映射,满足:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。称最小的数k为图G的(p,1)-全标号数。根据所构造图的特征,利用穷染法,得到了这些图的(2,1)-全标号数。     

关于图的(2,1)-全标号的几个结果

图G的(p,1)-全标号是与频道分配有关的一种染色问题,是从V(G)∪E(G)到集合{0,1,…,k}的一个映射,使得:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。(p,1)-全标号的跨度是指两个标号差的最大值。图G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λpT(G)。得到了几类有趣图的(2,1)-全标号数。     

两类图的（d，1）-全标号

图G的一个k-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为d．G的（d,1）-全标号数λ^Td（G）定义为G有一个k-（d,1）-全标号的最小的k值,得到了扇图与轮图的（d,1）-全标号数。     

几类圈构造图的(p,1)-全标号

一个图G的（p,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…k},使得：G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;一个点和它的邻边得到的整数至少相差p．（p,1）-全标号的跨度是指两个标号差的最大值．图G的（p,1）一全标号的最小跨度叫（p,1）-全标号数,记作λP^T（G）．给出了几类圈构造图的（p,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。     

轮图的（2，1）-全标号

图G的一个后-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同的值,且任一对相关联的点和边的值的差的绝对值至少为d．G的（d,1）-全标号数λd^T（G）定义为G有一个K-（d,1）-全标号的最小的k值,得到了轮图的（2,1）-全标号．     

围长至少为5的平面图的L（P，q）-标号

令Ap,q（G）为图G的L（p,g）-标号数,其中P和q是两个正整数且p≥q。证明了若G是围长g（G）≥5的平面图,则Ap,q（G）≤（2q-1）△（G）＋6p＋10q-8。由此导得对于g（G）≥5且△（G）≥16的平面图G,Wegner的猜想成立。     

图的（3，1）- 全标号

图G的(p,1)-全标号是对G的点和边进行标号,满足:任意两个相邻的点得到不同的标号,任意两个相邻的边得到的标号也不同.并且任意一个点与和它相关联的边所得到的标号的差的绝对值至少为p,其中在全标号中最大的标号与最小的标号的差值称为全标号的跨度,记一个(p,1)-全标号中最小的跨度为λTp.证明了当p=3,Δ(G)≥9时,λT3≤2Δ(G)+1.     

一类串图的1-维魔幻标号

如果有整数对(s_i,t_i)(i∈[1,m])和一一映f:V(G)∪E(G)→[1,p+q],对每一条边uv∈E(G),使得f(u)+f(v)=s_i+t_if(uv),则称f是图G的(s_i,t_i)~m_i=1-魔幻标号。进一步,若存在最小的正整数k,使得G的任何一个(s_i,t_i)~m_i=1-魔幻标号满足m≥k,则称G为k-维(s,t)-魔幻图。为此,定义了图G的魔幻全空间与向量空间,并用向量代数方法研究串图G,得到图G有1-维(s,t)-魔幻全标号。给出了1-维(s,t)-魔幻全标号与奇优美标号、对偶标号之间的关系,及用具有1-维-魔幻全标号的二部分(p,q)-图G来构造大规模的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)-标号数的确切值或上下界.     

某些特殊图类的非正常(p,1)-全标号

本文给出了图G的一个非正常(r,s,t)-(p,1)-全标号的定义,该标号基于图G的(p,1)-全标号,允许有破坏此限制条件的顶点和边.非正常(r,s,t)-(p,1)-全标号的跨度是指两个标号差的最大值.图G的非正常(r,s,t)-(p,1)-全标号的最小跨度称为图G的非正常(r,s,t)-(p,1)-全标号数,记作λT(r,s,t)(G;p,1).这里主要给出了某些特殊图类的非正常(2,2,0)-(p,1)-全标号的上界.     

几类联图的(2,1)-全标号

研究了与频道分配有关的一种染色问题——(p,1)-全标号。图G的(p,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,…,k},使得:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。(p,1)-全标号的跨度是指两个标号差的最大值。图G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λTp(G)。根据联图的特征,利用穷染法,得到了几类联图的(2,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)-标号数.     

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

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

外部平面图的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.     

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

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

CmP1Cn的优美性

设Cp表一个长为p的圈，CmP1Cn表示由一条1个点的路P1联结两个圈Cm和Cn得到的图，其中P1的内部顶点不在V（Cm）∪V（Cn）中，且当1＝1时，|V（Cm）∩V（Cn）|＝1；当1＞1时，|V（Cm）∩V（Cn）|＝0。本的目的是证明：CmP1Cn（l＝1，2，3）当4|m,4|n时，是k－优美图。     

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

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

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