Linear and cyclic distance-three labellings of trees

Abstract

Given a finite or infinite graph $G$ and positive integers $\ell, h_1, h_2, h_3$, an $L(h_1, h_2, h_3)$-labelling of $G$ with span $\ell$ is a mapping $f: V(G) \rightarrow \{0, 1, 2, \ldots, \ell\}$ such that, for $i = 1, 2, 3$ and any $u, v \in V(G)$ at distance $i$ in $G$, $|f(u) - f(v)| \geq h_i$. A $C(h_1, h_2, h_3)$-labelling of $G$ with span $\ell$ is defined similarly by requiring $|f(u) - f(v)|_{\ell} \ge h_i$ instead, where $|x|_{\ell} = \min\{|x|, \ell-|x|\}$. The minimum span of an $L(h_1, h_2, h_3)$-labelling, or a $C(h_1, h_2, h_3)$-labelling, of $G$ is denoted by $λ_{h_1,h_2,h_3}(G)$, or $σ_{h_1,h_2,h_3}(G)$, respectively. Two related invariants, $λ^*_{h_1,h_2,h_3}(G)$ and $σ^*_{h_1,h_2,h_3}(G)$, are defined similarly by requiring further that for every vertex $u$ there exists an interval $I_u$ $\mod~(\ell + 1)$ or $\mod~\ell$, respectively, such that the neighbours of $u$ are assigned labels from $I_u$ and $I_v \cap I_w = \emptyset$ 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 \ge p \ge 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 a few families of trees. We give sharp bounds on $σ_{h,p,p}(T)$ and $σ^*_{h,p,p}(T)$ for trees with maximum degree $Δ\le 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 $Δ\le h$.