國立臺灣大學數學系Chang, Gerard-JGerard-JChangChen, Jer-JeongJer-JeongChenKuo, DavidDavidKuoLiaw, Sheng-ChyangSheng-ChyangLiaw2006-09-272018-06-282006-09-272018-06-282004-07-08http://ntur.lib.ntu.edu.tw//handle/246246/20060927121137195236For positive integers j ≥ k, an L(j, k)-labeling of a digraph D is a function f from V (D) into the set of nonnegative integers such that |f(x) − f(y)| ≥ j if x is adjacent to y in D & |f(x) − f(y)| ≥ k if x is of distant two to y in D. Elements of the image of f are called labels. The 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)-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.application/pdf142129 bytesapplication/pdfzh-TWL(j,k)-labelingdigraphditreehomomorphismalgorithmjournal articlehttp://ntur.lib.ntu.edu.tw/bitstream/246246/20060927121137195236/1/arxiv-math-co-0407167.pdf