3≤m≤8,n≥6时射影平面网格图Gm,n的L（2,1）-标号

本文通过归纳综合的方法,研究了当3≤m≤8,n≥6时,射影平面网格图Gm,n的L(2,1)-标号问题,得到了以下结果:当3≤m≤8,n≥6时,Gm,n的L(2,1)-标号数的上界为9.

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)-边染色算法

图的距离染色问题是频率分配问题的一种图模型,所谓的频率分配问题是指某一区域的不同电台要使用无线电波发送信号,为了避免干扰,位置较近的电台需要使用不同的频道,当电台距离特别近时,它们之间需要间隔至少2个信道。L(2,1)-边染色是指距离为1的两条边的色数差值大于等于2,距离大于1的两条边的色数不同。本文针对随机图设计了一种L(2,1)-边染色算法,实验结果表明,该算法能够解决有限点内随机图的L(2,1)-边染色问题。通过分析实验结果,发现了3类单圈图的染色特性,定义C_(3)↑P_(n)↑S_(m),C_(n)↓S_(m)和C_(n)↑S_(m)分别来刻画这三类单圈图,并给出相关定理及其证明。

双圈连通图的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-hole L(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△+1或△+2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.

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

图的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)-标号

图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.不妨设最小标号为0.那么,图G的L(2,1)-标号数λ(G)是G的所有L(2,1)-标号下的跨度max{f(v);v∈V(G)}的最小值.定义了点接拟梯子,并完全确定了点接拟梯子的L(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)标号问题,并得到了平面三角剖分图、立体四面体剖分图的λ3(G)的上界。

两个完全二部图的匹配和的L(2,1)-标号

研究了两个均同构于完全二部图Km,n的图G1=(X1,Y1)与G2=(X2,Y2)的匹配和Bm,n的L(2,1)-标号问题,得到了下面的结果:(1)若X1中元素完全与X2中元素相匹配且m,n>3,则Bm,n的L(2,1)-标号数为m+n;(2)若X1中元素不完全与X2中元素相匹配且m,n>6,则Bm,n的L(2,1)-标号数为m+n+1.

连通度为k的图的L(2,1)-标号

通过找出图G的补图Gc的路覆盖数与其子图G-S的各个连通分支补图的路覆盖数间的关系,在图G的λ数与其补图Gc的路覆盖数之间关系的基础上,给出图G的λ数与子图G-S的各个连通分支补图的路覆盖数之间的关系(这里S是G的一个k-顶点割).

自补图的L(2,1)-标号

研究自补图G的L(2,1)-标号问题,证明了自补图的L(2,1)-标号数满足λ(G)≤2Δ。验证了关于一般图的L(2,1)-标号数的猜想λ(G)≤Δ2对于自补图的正确性。

Δ(G)=3的图的列表-L(2,1)-标号

记Δ(G)和λl(G)分别为图G的最大度和列表-L(2,1)-标号数.若Δ(G)≤3,则称G为子三次图.证明了若G是子三次图,那么λl(G)≤12;若G为最大平均度Mad(G)<8/3的子三次图,那么λl(G)≤10.这一结果进一步支撑了Griggs和Yeh关于距离2标号的猜想.

一个路与一个完全二部图直积的L(2,1)-标号

通过分类讨论,归纳综合的方法,研究一个路与一个完全二部图直积的L(2,1)-标号问题,得到以下的结果:(1)当n≥3时,P_3×K_(n,n)的L(2,1)-标号数为3n;(2)当n≥3时,P_4×K_(n,n)的L(2,1)-标号数为3n;(3)当m≥5,n≥3时,P_m×K_n,n的L(2,1)-标号数为3n+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 )_标号问题 ,并得出了Kneser图、高度不正则图、Halin图的λ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 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 。

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

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

关于n-格图及相关图的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 )标号问题 .将 2 格图及相关图推广到n 格图及相关图 ,并给出了它们的L(2 ,1 )标号 .

一个圈与一个完全二部图的直积的L(2,1)-标号

通过分类讨论、归纳综合的方法,研究了一个圈与一个完全二部图的直积的L(2,1)-标号问题,得到了以下的结果:(1)当n≥3时,C3×Kn,n的L(2,1)-标号数为3n+1;当n≥3时,C4×Kn,n的L(2,1)-标号数的上界是4n;当n≥3时,C5×Kn,n的L(2,1)-标号数为5n-1;(2)当n≥3,m≥6,m≡0(mod3)时,Cm×Kn,n的L(2,1)-标号数为3n+1;当n≥3,m≥6,m≡1(mod3)或m≡2(mod3)时,Cm×Kn,n的L(2,1)-标号数的上界是4n.

关于图的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) 标号问题 ,并得出了全图、块图的L(3,2 ,1) 标号数的上界 .