Distance-two labelings of digraphs

Details Distance-two labelings of digraphs Distance-two labelings of digraphs

2004-07-09

arxiv.org/abs/math/0407167v1

Mathematics

Combinatorics

12 pages; presented in SIAM Coference on Discrete Mathematics, June 13-16, 2004, Loews Vanderbilt Plaza Hotel, Nashville, TN,

Scientific paper

For positive integers $j\ge 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)|\ge j$ if $x$ is adjacent to $y$ in $D$ and $|f(x)-f(y)|\ge 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 $\vec{\lambda}_{j,k}$-number $\vec{\lambda}_{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 $\vec{\lambda}_{j,k}$- numbers of digraphs. In particular, we determine $\vec{\lambda}_{j,k}$- numbers of digraphs whose longest dipath is of length at most 2, and $\vec{\lambda}_{j,k}$-numbers of ditrees having dipaths of length 4. We also give bounds for $\vec{\lambda}_{j,k}$-numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining $\vec{\lambda}_{j,1}$-numbers of ditrees whose longest dipath is of length 3.

Affiliated with

Also associated with

No associations

Rating

Distance-two labelings of digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distance-two labelings of digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance-two labelings of digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-726042