关于图的距离标号问题  

The Distance Labeling Problem on Graphs

作　　者：邵振东[1] 刘家壮[2] 

机构地区：[1]哈尔滨工业大学深圳研究生院计算机科学与技术学科部,广东深圳518055 [2]山东大学数学研究所,山东济南250100

出　　处：《运筹与管理》2006年第4期44-46,共3页Operations Research and Management Science

摘　　要：图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(d1,d2,d3)-标号问题,并得出了复合图的λd1,d2,d3(G)的上界。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 so that ｜ f（x） - f（y） ｜ ≥2 if d （ x, y） = 1 and ｜ f（x） - f（y） ｜ ≥ 1 if d （ x, y） = 2. TheL （2, 1 ）-labeling number λ （G） of G is the smallest number k so that G has an L （2,1）-labeling with max { f（v） ： v ∈ V（G）}= k. We extend the L（2,1）labeling to the L（d1, d2, d3）-labeling and derive the upper bounds of λd1,d2,d3（G） of composition graph.

关 键 词：运筹学 频率分配 T-染色 L(2 1)-标号 

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