https://scholars.lib.ntu.edu.tw/handle/123456789/30221
Title: | Distance-two labelings of digraphs | Authors: | Chang, Gerard-J Chen, Jer-Jeong Kuo, David Liaw, Sheng-Chyang |
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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/20060927121137195236 | Other Identifiers: | 20060927121137195236 |
Appears in Collections: | 數學系 |
File | Description | Size | Format | |
---|---|---|---|---|
arxiv-math-co-0407167.pdf | 138.8 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.