## Abstract

For 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 and | 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)-labeling problem is to determine the over(λ, ⇒)_{j, k}-number over(λ, ⇒)_{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 over(λ, ⇒)_{j, k}-numbers of digraphs. In particular, we determine over(λ, ⇒)_{j, k}-numbers of digraphs whose longest dipath is of length at most 2, and over(λ, ⇒)_{j, k}-numbers of ditrees having dipaths of length 4. We also give bounds for over(λ, ⇒)_{j, k}-numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining over(λ, ⇒)_{j, 1}-numbers of ditrees whose longest dipath is of length 3.

Original language | English |
---|---|

Pages (from-to) | 1007-1013 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 155 |

Issue number | 8 |

DOIs | |

State | Published - 15 Apr 2007 |

## Keywords

- Algorithm
- Digraph
- Ditree
- Homomorphism
- L (j, k)-labeling