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

Abstract

Let 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 {maxu v ∈ E (T) min {d (u), d (v)} + h - 1, Δ2 (T) - 1} ≤ λh, 1, 1 (T) ≤ Δ2 (T) + h - 1, and both low..