THE L(2,1)-LABELING PROBLEM ON GRAPHS

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)\ gre ater 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 th at 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 uppe r 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 l ambda(G) less than or equal to Delta + 2 chi(G) - 2. Finally, we prese nt a polynomial time algorithm to determine lambda(T) for a tree T.