Distance-two labelings of digraphs

Abstract

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.

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