L(2,1,1)-labeling is NP-complete for trees.

Abstract

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