关于图的L(d_1，d_2)-标号问题(英文)  

The L(d_1, d_2)-Labeling Problem on Graphs

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

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

出　　处：《工程数学学报》2006年第3期559-562,共4页Chinese Journal of Engineering Mathematics

摘　　要：图的L(2,1)-标号问题是由频率分配问题归结而来,本文研究作为L(2,1)-标号问题的推广的L(d_1,d_2)-标号问题。首先定义了顶点2-着色,2-色数及其它有关概念,给出了2-色数的上界。然后得出了λ_(d_1,d_2)(G)与δ(G)和Δ(G)的一般关系。最后得出了一般图与平面图的λ_(d_1,d_2)(G)的上界。The L（2, 1）-labeling is formulated from the frequency assignment problem. We study the L（d1, d2）- labeling which is a generalization of the L（2, 1）-labeling. Vertex 2-coloring, 2- chromatic number and other related concepts are firstly defined, and the upper bound for 2-chromatic number is given; a very general relationship between λd1,d2 （G） and minimum degree δ（G） and maximum degree △（G） is then derived; finally, the upper bounds of L（d1, d2）-labelings of general and planar graphs are given.

关 键 词：L(d1 d2)-标号 顶点2-着色 2-色数 

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