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)\to \{0,1,2,\dots ,\ell \}$ such that, for $i=1,2,3$ and any $u,v\in V(G)$ at distance $i$ in $G$, $|f(u)-f(v)|\ge 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 ${\lambda }_{h_1,h_2,h_3}(G)$, or ${\sigma }_{h_1,h_2,h_3}(G)$, respectively. Two related invariants, ${\lambda }_{h_1,h_2,h_3}^{\ast }(G)$ and ${\sigma }_{h_1,h_2,h_3}^{\ast }(G)$, are defined similarly by requiring further that for every vertex $u$ there exists an interval $I_u$ $\mathrm{mod}(\ell +1)$ or $\mathrm{mod}\ell$, respectively, such that the neighbours of $u$ are assigned labels from $I_u$ and $I_v\cap I_w=\varnothing$ 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 ${\lambda }_{h,p,p}(T)$, ${\lambda }_{h,p,p}^{\ast }(T)$, ${\sigma }_{h,1,1}(T)$ and ${\sigma }_{h,1,1}^{\ast }(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 ${\sigma }_{h,p,p}(T)$ and ${\sigma }_{h,p,p}^{\ast }(T)$ for trees with maximum degree $\Delta \le h/p$, and as a special case we obtain that ${\sigma }_{h,1,1}(T)={\sigma }_{h,1,1}^{\ast }(T)=2h+\Delta -1$ for any tree $T$ with $\Delta \le h$.

Cited by in corpus (2)

• Distance-constrained labellings of Cartesian products of graphs
• Distance labellings of Cayley graphs of semigroups