The L(h,1,1)-labelling problem for trees

AbstractLet h≥1 be an integer. An L(h,1,1)-labelling of a (finite or infinite) graph is an assignment of nonnegative integers (labels) to its vertices such that adjacent vertices receive labels with difference at least h, and vertices distance 2 or 3 apart receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(h,1,1)-labellings is called the λh,1,1-number of the graph. We prove that, for any integer h≥1 and any finite tree T of diameter at least 3 or infinite tree T of finite maximum degree, max{maxuv∈E(T)min{d(u),d(v)}+h−1,Δ2(T)−1}≤λh,1,1(T)≤Δ2(T)+h−1, and both lower and upper bounds are attainable, where Δ2(T) is the maximum total degree of two adjacent vertices. Moreover, if h is less than or equal to the minimum degree of a non-pendant vertex of T, then λh,1,1(T)≤Δ2(T)+h−2. In particular, Δ2(T)−1≤λ2,1,1(T)≤Δ2(T). Furthermore, if T is a caterpillar and h≥2, then max{maxuv∈E(T)min{d(u),d(v)}+h−1,Δ2(T)−1}≤λh,1,1(T)≤Δ2(T)+h−2 with both lower and upper bounds achievable