The L(2,1)-labeling problem on graphs

Abstract

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.