毛毛虫树的最优$L(2,1,1)$-标号

图$G$的一个$L(2,1,1)$-标号是指从顶点集$V(G)$到非负整数集上的一个函数$f$,满足: 当$d(u,v)=1$时, $|f(u)-f(v)|ge 2$, 当$d(u,v)=2$时, $|f(u)-f(v)|ge 1$, 当$d(u,v)=3$时, $|f(u)-f(v)|ge 1$. 若一个$L(2,1,1)$-标号中的所有像元素都不超过整数$k$, 则称之为图$G$的$k$-$L(2,1,1)$-标号. 图$G$的$L(2,1,1)$-标号数, 记作$lambda 2,1,1(G)$,是使得图$G$存在$L(2,1,1)$-标号的最小整数$k$. 本文研究了毛毛虫树的最优$L(2,1,1)$-标号,给出了一些$L(2,1,1)$-标号数达到上界的充分条件,并完全刻画了最大边度为6的毛毛虫树的$L(2,1,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 数的界.     

图的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(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(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(z，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)|=κ的L(2，1)-标号中的最小数κ。本将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)标号问题，并得到了平面三角剖分图、立体四面体剖分图的λ3(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)的上界 .     

最大度为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(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为扇图的路上每个...     

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

关于图的距离标号问题

图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）的上界。     

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 $d_G(u, v)=1$, $|f(u)−f(v)|≥2$ if $d_G(u, v)=2$, and $|f(u)−f(v)|≥1$ if $d_G(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(^{0,1,2}_{d,d,1})$-标号数上界

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

圈的$L(d_1,d_2,ldots,d_t)$-数$lambda(C_n;d_1,d_2,ldots,d_t)$

An L（d0,d2,...,dt）-labeling of a graph G is a function f from its vertex set V（G） to the set {0,1,..., k} for some positive integer k such that If（x） - f（y）l ≥di, if the distance between vertices x and y in G is equal to i for i = 1,2,...,t. The L（d1,d2,...,dt）-number λ（G;d1,d2,... ,dt） of G is the smallest integer number k such that G has an L（d1,d2,...,dr）- labeling with max{f （x）｜x ∈ V（G）} = k. In this paper, we obtain the exact values for λ（Cn; 2, 2, 1） and λ（Cn; 3, 2, 1）, and present lower and upper bounds for λ（Cn; 2,..., 2, 1,..., 1）     

Frequency Assignment through Combinatorial Optimization Approach

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)|(?)2 if d(x, y)=1 and |f(x)-f(y)|(?)1 if d(x,y)=2. The L(2,1)-labeling numberλ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v) : v∈V(G)}=k. We study the L(3,2,1)-labeling which is a generalization of the L(2,1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds ofλs(G) of the graph.     

双圈连通图的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的存在性.     

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.