A note on L(2, 1)-labelling of trees
A note on L(2, 1)-labelling of trees
复制标题
DOI：
10.1007/s10255-012-0151-9
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
M. Zhai;Changhong Lu;Jinlong Shu
中科院分区：
文献类型：
--
作者：
M. Zhai;Changhong Lu;Jinlong Shu
图G的L（2，1）-标号是从顶点集V（G）到所有非负整数的集合的函数，使得|f（u）−f（v）|≥ 2 ifdG（u，v）= 1，且|f（u）−f（v）|≥ 1 ifdG（u，v）= 2。L（2，1）-标号问题是寻找一个最小的数λ（G），使得存在一个L（2，1）-标号函数，没有标号大于它.本文研究树的L（2，1）-标号问题.我们的结果改进了Wang [TheL（2，1）-labeling of trees，Discrete Appl.Math.154（2006）598-603]的结果。
AnL(2, 1)-labelling of a graphGis a function from the vertex setV(G) to the set of all nonnegative integers such that |f(u) −f(v)| ≥ 2 ifdG(u, v) = 1 and |f(u) −f(v)| ≥ 1 ifdG(u, v) = 2. TheL(2, 1)-labelling problem is to find the smallest number, denoted byλ(G), such that there exists anL(2, 1)-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [TheL(2, 1)-labelling of trees, Discrete Appl. Math. 154 (2006) 598–603].