Labeling trees with a condition at distance two

An L(h, k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h, k)-labeling is the difference between the largest and the smallest label. We investigate L(h, k)-labelings of trees of maximum degree Delta, seeking those with small span. Given Delta, h and k, span lambda is optimal for the class of trees of maximum degree Delta, if lambda is the smallest integer such that every tree of maximum degree Delta has an L(h, k)-labeling with span at most lambda. For all parameters Delta, h, k, such that h < k, we construct L(h, k)-labelings with optimal span. We also establish optimal span of L(h, k)-labelings for stars of arbitrary degree and all values of h and k. (c) 2006 Elsevier B.V. All rights reserved.