Linear and cyclic distance-three labellings of trees

Given a finite or infinite graph G and positive integers ℓ,h1,h2,h3, an L(h1,h2,h3)-labelling of G with span ℓ is a mapping f:V(G)→{0,1,2,…,ℓ} such that, for i=1,2,3 and any u,v∈V(G) at distance i in G, |f(u)−f(v)|≥hi. A C(h1,h2,h3)-labelling of G with span ℓ is defined similarly by requiring |f(u)−f(v)|ℓ≥hi instead, where |x|ℓ=min{|x|,ℓ−|x|}. The minimum span of an L(h1,h2,h3)-labelling, or a C(h1,h2,h3)-labelling, of G is denoted by λh1,h2,h3(G), or σ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 u there exists an interval Iumod(ℓ+1) or modℓ, respectively, such that the neighbours of u are assigned labels from Iu and Iv∩Iw=0̸ for every edge vw of G. A recent result asserts that the 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) and C(h,p,p) labelling problems for finite or infinite trees T with finite maximum degree, where h≥p≥1 are integers. We give sharp bounds on λh,p,p(T), λh,p,p∗(T), σh,1,1(T) and σh,1,1∗(T), together with linear time approximation algorithms for the L(h,p,p)-labelling and the C(h,1,1)-labelling problems for finite trees. We obtain the precise values of these four invariants for complete m-ary trees with height at least 4, the infinite complete m-ary tree, and the infinite (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) and σh,p,p∗(T) for trees with maximum degree Δ≤h/p, and as a special case we obtain that σh,1,1(T)=σh,1,1∗(T)=2h+Δ−1 for any tree T with Δ≤h.