TY - JOUR

T1 - Distance-two labelings of digraphs

AU - Chang, Gerard J.

AU - Chen, Jer Jeong

AU - Kuo, David

AU - Liaw, Sheng Chyang

PY - 2007/4/15

Y1 - 2007/4/15

N2 - 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.

AB - 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.

KW - Algorithm

KW - Digraph

KW - Ditree

KW - Homomorphism

KW - L (j, k)-labeling

UR - http://www.scopus.com/inward/record.url?scp=33947250136&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2006.11.001

DO - 10.1016/j.dam.2006.11.001

M3 - 期刊論文

AN - SCOPUS:33947250136

SN - 0166-218X

VL - 155

SP - 1007

EP - 1013

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 8

ER -