首页 | 本学科首页   官方微博 | 高级检索  
     检索      

有向图的L(j,k)数的上界
引用本文:翟明清,吕长虹.有向图的L(j,k)数的上界[J].运筹学学报,2007,11(4):65-69.
作者姓名:翟明清  吕长虹
作者单位:1. 华东师范大学,数学系,上海,200062;滁州学院数学系,滁州,239012
2. 华东师范大学,数学系,上海,200062;华东师范大学计算机理论研究所,上海,200062
基金项目:国家自然科学基金;安徽省教育厅自然科学基金
摘    要:给定正整数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的一个有效算法.

关 键 词:运筹学  L(j  k)-标号  有向图  有向路  算法
收稿时间:2006-05-08
修稿时间:2006年5月8日

The Upper Bound of L(j,k)-Number of Digraphs
Zhai Mingqing,Lü Changhong.The Upper Bound of L(j,k)-Number of Digraphs[J].OR Transactions,2007,11(4):65-69.
Authors:Zhai Mingqing  Lü Changhong
Abstract: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 l,if it has no dicycle or the longest dicycle in D is of length l+1,then →λj,k(D)≤lj.Moreover these bounds ore sharp.Finally,we present an efficient algorithm for assigning all 3j-L(j,K)-labelling to digraphs whose longest dipath is of length 3.
Keywords:Operations research  L(j  k)-labelling  digraph  dipath  algorithm
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号