Optimal L (3,2,1)-labeling of trees

Given a graph G, an L(3,2,1)-labeling of G is an assignment f of non-negative integers (labels) to the vertices of G such that |f(u)−f(v)|≥4−i if dist(u,v)=i (i = 1, 2, 3). For a non-negative integer k, a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k. The L(3,2,1)-labeling number of G, denoted by λ3,2,1(G), is the smallest number k such that G has a k-L(3,2,1)-labeling. Chia proved that the L(3,2,1)-labeling number of a tree T with maximum degree Δ can have one of three values: 2Δ+1, 2Δ+2 and 2Δ+3. This paper gives some sufficient conditions for λ3,2,1(T)≥2Δ+2 and λ3,2,1(T)=2Δ+3, respectively. As a result, the L(3,2,1)-labeling numbers of complete m-ary trees, spiders and banana trees are completely determined.