Abstract
An L(p(1), p(2), p(3))-labeling of a graph G with span lambda is a mapping f that assigns each vertex u of G an integer label 0 = p(i) whenever vertices u and v are of distance i for i is an element of {1, 2, 3}. We show that testing whether a given graph has an L(2, 1, 1)-labeling with some given span lambda is NP-complete even for the class of trees.