Distance-two labelings of digraphs
| dc.creator | Chang, G. J. | |
| dc.creator | Chen, J. -J. | |
| dc.creator | Kuo, D. | |
| dc.creator | Liaw, S. C. | |
| dc.date | 2004-07-09 | |
| dc.date.accessioned | 2026-07-07T05:10:09Z | |
| dc.date.available | 2026-07-07T05:10:09Z | |
| dc.description | 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λ_{j,k}$-number $\vecλ_{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λ_{j,k}$- numbers of digraphs. In particular, we determine $\vecλ_{j,k}$- numbers of digraphs whose longest dipath is of length at most 2, and $\vecλ_{j,k}$-numbers of ditrees having dipaths of length 4. We also give bounds for $\vecλ_{j,k}$-numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining $\vecλ_{j,1}$-numbers of ditrees whose longest dipath is of length 3. | |
| dc.description | 12 pages; presented in SIAM Coference on Discrete Mathematics, June 13-16, 2004, Loews Vanderbilt Plaza Hotel, Nashville, TN, USA | |
| dc.identifier | https://arxiv.org/abs/math/0407167 | |
| dc.identifier | http://arxiv.org/abs/math/0407167 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71840 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C78; 05C15; 05C85 | |
| dc.title | Distance-two labelings of digraphs | |
| dc.type | text |