The L(2,1)-labelling of trees

An L(2, 1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices have numbers at least 2 apart, and vertices at distance 2 have distinct numbers. The L(2,1)-labelling number lambda(G) of G is the minimum range of labels over all such labellings. It was shown by Griggs and Yeh [Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595] that every tree T has Delta + 1 <= lambda(T) <= Delta + 2. This paper prov ides a sufficient condition for lambda(T) = Delta + 1. Namely, we prove that if a tree T contains no two vertices of maximum degree at distance either 1, 2, or 4, then lambda(T) = Delta + 1. Examples of trees T with two vertices of maximum degree at distance 4 such that lambda(T) = Delta + 2 are constructed. (c) 2005 Elsevier B.V. All rights reserved.