有向图的L(j,k)数的上界(英文)  

The Upper Bound of L(j, k)-Number of Digraphs

作　　者：翟明清[1] 吕长虹[1] 

机构地区：[1]华东师范大学数学系

出　　处：《运筹学学报》2007年第4期65-69,共5页Operations Research Transactions

基　　金：Supported by National Natural Science Foundation of China (No.10301010 and No.60673048);Natural Science Foundation of Education Ministry of Anhui Province (NO.KJ2007B124).

摘　　要：给定正整数j≥k,有向图D的一个L(j,k)-标号是指从V(D)到非负整数集的一个函数f,使得当x在D中邻接到y时|f(x)-f(y)|≥j,当x在D中到y距离为二时|f(x)-f(y)|≥k.f的像元素称为标号.L(j,k)一标号问题就是确定(?)j,k-数(?)j,k(D),这个参数等于(?) max{f(x)|x∈V(D)},这里f取遍D的所有L(j,k)-标号.本文根据有向图的有向着色数及最长有向路的长度来研究(?)j,k-数,证明了:(1)对任何有向着色数为(?)(D)的有向图D,(?)j,k(D)≤((?)(D)-1)j;(2)对任何最长有向路的长度为l的有向图D,如果不含有向圈或者D中最长有向圈长度为l+1,则(?)j,k(D)≤lj.并且这两个界都是可达的.最后我们对l=3的有向图给出了3j-L(j,k)-labelling的一个有效算法.For positive integers j≥k, an L（j, k）-labelling of a digraph D is a function f from V（D） into the set of nonnegative integers such that ｜f（x） - f（y）｜≥j if x is adjacent to y in D and ｜f（x） - f（y）｜≥k if x is of distance two to y in D. Elements of the image of f are called labels. The L（j, k）-labelling problem is to determine the （？） j,k-number （？）j,k（D）, which is the minimum of the maximum label used in an L（j,k）-labelling of D. This paper studies （？）j,k-numbers of digraphs according to its oriented chromatic number and the length of their longest dipaths. It is shown that： （1） For any digraph D with its oriented chromatic number （？）（D）, （？）j,k（D）≤（（？）（D） - 1）j; （2） For any digraph D whose longest dipath is of length 2, if it has no dicycle or the longest dicycle in D is of length l ＋ 1, then （？）j,k（D）≤lj. Moreover these bounds are sharp. Finally, we present an efficient algorithm for assigning an 3j-L（j,k）-labelling to digraphs whose longest dipath is of length 3.

关 键 词：运筹学 L(j k)-标号 有向图 有向路 算法 

分 类 号：O157.5[理学—数学] O157[理学—基础数学]