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

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

无向图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射,满足:对i=1,2,3,只要dG(x,y)=i,则f(x)-f(y)|≥4-i.若一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作3λ(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.文中给出了路、圈、树等特殊图的L(3,2,1)-标号数,并给出了一般图的L(3,2,1)-标号数的一个上界.     

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

关于图的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 )标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .     

点接手镯图的L(1,1,1)-标号

图的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)的最小数为图的L(1,1,1)-标号数,记为λ(G).基本给出了点接手镯图的L(1,1,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 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

竖梯的局部替换图的L(d,1,1)-标号

图的L(d,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1时,均有|f(u)-f(v)|≥d,当d(u,v)=2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(d,1,1)-标号中的最大跨度max{f(v):v∈V(G)}的最小数为图的L(d,1,1)-标号数,记为λ_d(G).基本给出了竖梯的局部替换图的L(d,1,1)-标号数的确切值或界.     

一类裂变图的L(0,1,2 d,d,1)-标号数上界

将图的标号问题由每个顶点需要一个标号的情况推广到每个顶点需要多个标号的情况,给出裂变图的概念以及赋权图的L(0,1,2 d,d,1)-标号的概念,给出R-单位球图对应裂变图的L(0,1,2 d,d,1)-标号数的一个上界.     

弦图的L(3,2,1)}-标号

图 G 的一个 L(3,2,1)- 标号是指从 V(G) 到非负整数集的一个映射 f, 满足: 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 3; 当 d_G(u,v)=2 时, |f(u)-f(v)|\geq 2; 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 1. L(3,2,1)-标号问题就是确定出最小的整数 \lambda_3(G) 使得 G存在最大标号不超过该数的 L(3,2,1)- 标号. 本文研究了弦图的 L(3,2,1)- 标号问题,获得了弦图及其一些子类, 如扇, r- 路,r- 树等的 \lambda_3 数的界.     

两类图的(d,1)-全标号

主要讨论了W_n与C_m的笛卡尔积和均衡完全r-部图K_r(n)的(d,1)-全标号,并得出了(d,1)-全数λ_d~T(W_n□C_m)和λ_d~T(K_(r(n)))的确切值.     

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

外平面图是没有子图为K₄或K_2,3的剖分的图。设G为一个外平面图,本文证明了G的L(2,1)标号数λ(G)≤Δ(G)+9。     

最大度至多为6的平面图的L(2,1)-标号

令Δ(G),g(G)和λ(G)分别为图G的最大度,围长,和L(2,1)-标号数.证明了若G是Δ(G)≤6和g(G)≥5的平面图,则λ(G)≤Δ(G)+13.进而关于Δ(G)≤6和g(G)≥5的平面图G,这个界要比先前的结果好.     

最大度为3的树的L(2,1)-标号数的一个刻画

图G的一个L(2,1)-标号是对G顶点集合的一个非负整数分配,使得其中相邻的点取得的整数差值至少为2并且距离为2的点取得不同的整数.L(2,1)-标号数就是所有这样的标号分配中最小的标号跨度值.Griggs和Yeh的[Labelling graphs with a condition at distance 2,SIAM J.Discrete Math.,1992,5:586-595]已经证明了,一棵树的L(2,1)-标号数不是△就是△+1.对于最大度为3的树的L(2,1)-标号数,本文给出了一个完全的刻画.     

一类裂变图的L(_(d,d,1)~(0,1,2))-标号数上界

将图的标号问题由每个顶点需要一个标号的情况推广到每个顶点需要多个标号的情况,给出裂变图的概念以及赋权图的L(_(d,d,1)~(0,1,2))-标号的概念,给出R-单位球图对应裂变图的L(_(d,d,1)~(0,1,2))-标号数的一个上界。     

The L（3,2, 1）-labeling on Bipartite Graphs

An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.     

双圈连通图的L(2,1)-labelling

给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.