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

Let h≥1h≥1 be an integer. An L(h,1,1)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 hh, 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)L(h,1,1)-labellings is called the λh,1,1λh,1,1-number of the graph. We prove that, for any integer h≥1h≥1 and any finite tree TT of diameter at least 3 or infinite tree TT 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−1max{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)Δ2(T) is the maximum total degree of two adjacent vertices. Moreover, if hh is less than or equal to the minimum degree of a non-pendant vertex of TT, then λh,1,1(T)≤Δ2(T)+h−2λh,1,1(T)≤Δ2(T)+h−2. In particular, Δ2(T)−1≤λ2,1,1(T)≤Δ2(T)Δ2(T)−1≤λ2,1,1(T)≤Δ2(T). Furthermore, if TT is a caterpillar and h≥2h≥2, then max{maxuv∈E(T)min{d(u),d(v)}+h−1,Δ2(T)−1}≤λh,1,1(T)≤Δ2(T)+h−2max{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.