图的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)-标号数的一个上界.     

关于图的距离标号问题

图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）-标号中的最小数愚。本文将L（2，1）-标号问题推广到更一般的情形即L（d1，d2，d3）-标号问题，并得出了复合图的λd1，d2，d3（G）的上界。     

关于图的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(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 数的界.     

关于图的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(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。移动通讯频率分配问题可以转化为图的L（2，1）标号问题。本文首先给出平面格子图的L（2，1）标号，然后通过平面格子图及相关图的L（2，1）标号得到平面近正六边形剖分图的L（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 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

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

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

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

An L(3,2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all non-negative integers(labels) such that |f(u)-f(v)|≥3 if d(u,v)=1,|f(u)-f(v)≥2 if d(u,v)=2 and |f(u)-f(v)|≥1 if d(u,v)=3.For a non-negative integer k,a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k.The L(3,2,1)-labeling number of G,denoted by λ_(3,2,1)(G), is the smallest number k such that G has a k-L(3,2,1)-labeling.In this article,we characterize the L(3,2,1)-labeling numbers of trees with diameter at most 6.     

关于图的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.     

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

图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.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f (v):v∈V(G)}的最小数.图F*n+1为扇图的路上每个...     

最大度至多为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,这个界要比先前的结果好.