The L(2,1)-labeling and operations of graphs

Motivated by a variation of the channel assignment problem, a graph labeling analogous to the graph vertex coloring has been presented and is called an L(2,1)-labeling. More precisely, 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)|>2 if d(x,y)=1 and |f(x)-f(y)| >1 if d(x,y) = 2. The L (2,1)-labeling number (lambda)(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v(is a member of)V (G)}=k. A conjecture states that (lambda)(G) <(Delta)/sup 2/ for any simple graph with the maximum degree (Delta)>2. This paper considers the graphs formed by the Cartesian product and the composition of two graphs. The new graph satisfies the conjecture above in both cases(with minor exceptions).