Distance-two labelings of digraphs (Q881579)

Let \(D\) be a digraph and let \(j\geq k>0\) be integers. An \(L(j,k)\)-labeling of \(D\) is a function from \(V(D)\) to the set of nonnegative integers such that for all \(x,y\in V(D)\), (i) if \(y\) is at distance one from \(x\), then \(| f(x)-f(y)| \geq j\); and (ii) if \(y\) is at distance two from \(x\), then \(| f(x)-f(y)| \geq k\). The value \(f(x)\) is called the label of \(x\) (given by \(f\)). If \(f\) is an \(L(j,k)\)-labeling of \(D\), let \(m_{j,k}(f)\) be the maximum of the labels given by \(f\). The number \(\vec{\lambda}_{j,k}(D)\) is defined as the minimum of the numbers \(m_{j,k}(f)\) for all the \(L(j,k)\)-labelings of \(D\). The authors show the following properties of the numbers \(\vec{\lambda}_{j,k}(D)\), where \(\ell(D)\) denotes the length of the longest dipath in \(D\). (1) If \(\ell(D)=2\) and \(D\) is bipartite, then \(\vec{\lambda}_{j,k}(D)=j+k\); (2) if \(\ell(D)=2\) and \(D\) is not bipartite, then \(\vec{\lambda}_{j,k}(D)=2j\); (3) if \(\ell(D)=3\) and \(D\) is bipartite, then \(j+k\leq \vec{\lambda}_{j,k}(D)=j+2k\); (4) if \(T\) is a ditree, then \(\vec{\lambda}_{j,k}(T)\leq\min\{2j, j+2k\}\), and the equality holds if \(\ell(D)=4\). Finally, the authors present a linear-time algorithm for determining \(\vec{\lambda}_{j,k}(T)\) if \(T\) is a ditree with \(\ell(T)=3\).