https://scholars.lib.ntu.edu.tw/handle/123456789/30221
標題: | Distance-two labelings of digraphs | 作者: | Chang, Gerard-J Chen, Jer-Jeong Kuo, David Liaw, Sheng-Chyang |
關鍵字: | L(j,k)-labeling;digraph;ditree;homomorphism;algorithm | 公開日期: | 8-七月-2004 | 卷: | v1 | 起(迄)頁: | - | 來源出版物: | math.CO/0407167 | 摘要: | 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 | 其他識別: | 20060927121137195236 |
顯示於: | 數學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
arxiv-math-co-0407167.pdf | 138.8 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。