標題: The L(2,1)-labeling problem on graphs
作者: Chang, GJ
Kuo, D
交大名義發表
應用數學系
National Chiao Tung University
Department of Applied Mathematics
關鍵字: L(2,1)-labeling;T-coloring;union;join;chordal graph;perfect graph;tree;bipartite matching;algorithm
公開日期: 1-五月-1996
摘要: An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that f(x) - f(y) greater than or equal to 2 if d(x, y) = 1 and f(x) - f(y) greater than or equal to 1 if d(x, y) = 2. The L(2, 1)-labeling number lambda(G) of G is the smallest number Ic such that G has an L(2, 1)-labeling with max{f(v) : v is an element of V(G)} = k. In this paper, we give exact formulas of lambda(G boolean OR H) and lambda(G + H). We also prove that lambda(G) less than or equal to Delta(2) + Delta for any graph G of maximum degree Delta. For odd-sun-free (OSF)-chordal graphs, the upper bound can be reduced to lambda(G) less than or equal to 2 Delta + 1. For sun-free (SF)-chordal graphs, the upper bound can be reduced to lambda(G) less than or equal to Delta + 2 chi(G) - 2. Finally, we present a polynomial time algorithm to determine lambda(T) for a tree T.
URI: http://hdl.handle.net/11536/1295
ISSN: 0895-4801
期刊: SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume: 9
Issue: 2
起始頁: 309
結束頁: 316
顯示於類別:期刊論文


文件中的檔案:

  1. A1996UL33300013.pdf