|Title:||Distance-two labelings of digraphs||Authors:||Chang, Gerard-J
|Keywords:||L(j,k)-labeling;digraph;ditree;homomorphism;algorithm||Issue Date:||8-Jul-2004||Journal Volume:||v1||Start page/Pages:||-||Source:||math.CO/0407167||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.
|Appears in Collections:||數學系|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.