Distance-two labelings of digraphs

For positive integers j⩾kj⩾k, an L(j,k)L(j,k)-labeling of a digraph D is a function f   from V(D)V(D) into the set of nonnegative integers such that |f(x)-f(y)|⩾j|f(x)-f(y)|⩾j if x is adjacent to y in D   and |f(x)-f(y)|⩾k|f(x)-f(y)|⩾k if x is of distance two to y in D. Elements of the image of f   are called labels. The L(j,k)L(j,k)-labeling problem is to determine the λ⇒j,k-number λ⇒j,k(D) of a digraph D  , which is the minimum of the maximum label used in an L(j,k)L(j,k)-labeling of D  . This paper studies λ⇒j,k-numbers of digraphs. In particular, we determine λ⇒j,k-numbers of digraphs whose longest dipath is of length at most 2, and λ⇒j,k-numbers of ditrees having dipaths of length 4. We also give bounds for λ⇒j,k-numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining λ⇒j,1-numbers of ditrees whose longest dipath is of length 3.