Search

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