Linear and cyclic distance-three labellings of trees

Given a finite or infinite graph GG and positive integers l,h1,h2,h3l,h1,h2,h3, an L(h1,h2,h3)L(h1,h2,h3)-labelling of GG with span ll is a mapping f:V(G)→{0,1,2,…,l}f:V(G)→{0,1,2,…,l} such that, for i=1,2,3i=1,2,3 and any u,v∈V(G)u,v∈V(G) at distance ii in GG, |f(u)−f(v)|≥hi|f(u)−f(v)|≥hi. A C(h1,h2,h3)C(h1,h2,h3)-labelling of GG with span ll is defined similarly by requiring |f(u)−f(v)|l≥hi|f(u)−f(v)|l≥hi instead, where |x|l=min{|x|,l−|x|}|x|l=min{|x|,l−|x|}. The minimum span of an L(h1,h2,h3)L(h1,h2,h3)-labelling, or a C(h1,h2,h3)C(h1,h2,h3)-labelling, of GG is denoted by λh1,h2,h3(G)λh1,h2,h3(G), or σh1,h2,h3(G)σh1,h2,h3(G), respectively. Two related invariants, λh1,h2,h3∗(G) and σh1,h2,h3∗(G), are defined similarly by requiring further that for every vertex uu there exists an interval Iumod(l+1) or modl, respectively, such that the neighbours of uu are assigned labels from IuIu and Iv∩Iw=0Iv∩Iw=0 for every edge vwvw of GG. A recent result asserts that the L(2,1,1)L(2,1,1)-labelling problem is NP-complete even for the class of trees. In this paper we study the L(h,p,p)L(h,p,p) and C(h,p,p)C(h,p,p) labelling problems for finite or infinite trees TT with finite maximum degree, where h≥p≥1h≥p≥1 are integers. We give sharp bounds on λh,p,p(T)λh,p,p(T), λh,p,p∗(T), σh,1,1(T)σh,1,1(T) and σh,1,1∗(T), together with linear time approximation algorithms for the L(h,p,p)L(h,p,p)-labelling and the C(h,1,1)C(h,1,1)-labelling problems for finite trees. We obtain the precise values of these four invariants for complete mm-ary trees with height at least 4, the infinite complete mm-ary tree, and the infinite (m+1)(m+1)-regular tree and its finite subtrees induced by vertices up to a given level. We give sharp bounds on σh,p,p(T)σh,p,p(T) and σh,p,p∗(T) for trees with maximum degree Δ≤h/pΔ≤h/p, and as a special case we obtain that σh,1,1(T)=σh,1,1∗(T)=2h+Δ−1 for any tree TT with Δ≤hΔ≤h.