Distance-two labelings of digraphs
Resource
Discrete Applied Mathematics 155 (8): 1007-1013
Journal
Discrete Applied Mathematics
Journal Volume
155
Journal Issue
8
Pages
1007-1013
Date Issued
2007
Author(s)
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. © 2006 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
10.pdf
Size
24.19 KB
Format
Adobe PDF
Checksum
(MD5):beeb2b67ed6afff9929a470c6646a71d