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

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

图的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.