A characterization of λd, 1-minimal trees and other attainable classes

Abstract

An L (j, k)-labeling of a graph G, where j ≥ k, is defined as a function f : V (G) → Z+ ∪ {0} such that if u and v are adjacent vertices in G, then | f (u) - f (v) | ≥ j, while if u and v are vertices such that the length of the shortest path joining them is two, then | f (u) - f (v) | ≥ k. The largest label used by f is the span of f. The smallest span among all L (j, k)-labelings of G is denoted by λj, k (G). Let T be any tree of maximum degree Δ and let d ≥ 2 be a positive integer. Then, for every c ∈ {1, ..., min {Δ, d}}, T is in class c if λd, 1 (T) = Δ + d + c - 2. We characterize the class c of trees for every such c and also show that this class is non-empty. © 2008 Elsevier B.V. All..