標題: The L(2,1)-labeling problem on graphs 作者: Chang, GJKuo, D交大名義發表應用數學系National Chiao Tung UniversityDepartment 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 顯示於類別： 期刊論文