On L(2,1)-labellings of distance graphs  

关于距离图的L(2,1)-标号着色(英文)

作　　者：陶昉昀[1] 顾国华[2] 许克祥[3] 

机构地区：[1]南京林业大学信息科学技术学院数学系,南京210037 [2]东南大学数学系,南京210096 [3]南京航空航天大学理学院,南京210016

出　　处：《Journal of Southeast University(English Edition)》2005年第2期244-248,共5页东南大学学报（英文版）

基　　金：TheNationalNaturalScienceFoundationofChina(No. 10171013)

摘　　要：The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.研究了距离图G(D)的L(2, 1) 标号色数λ(D).证明了距离图满足λ(G)≤Δ2.对于任意给定的正整数k,证明了λ({1, 2, , k}) =2k+2和λ({1, 3 , 2k-1 }) =2k+2.假设k,a∈N且k,a≥2.如果k≥a,则λ({a,a+1, ,a+k-1})=2(a+k-1).否则,λ({a,a+1, ,a+k-1})≤min{2(a+k-1),6k-2}.若D由2个正整数构成,则6≤λ(D)≤8.对于特殊的距离集D={k,k+1}( k∈N),λ(D)的上界改进到了7.

关 键 词：channel assignment problem L(2 1)-labelling distance graphs 

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