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 -