Distance-two labelings of digraphs
Resource
math.CO/0407167 v1
Journal
math.CO/0407167
Journal Volume
v1
Pages
-
Date Issued
2004-07-08
Date
2004-07-08
Author(s)
Chang, Gerard-J
Chen, Jer-Jeong
Kuo, David
Liaw, Sheng-Chyang
DOI
20060927121137195236
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 & |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.
Subjects
L(j,k)-labeling
digraph
ditree
homomorphism
algorithm
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
arxiv-math-co-0407167.pdf
Size
138.8 KB
Format
Adobe PDF
Checksum
(MD5):a35fb0d7a55e3bad3afab6f00dac4710