L(2,1)-Labelings on the composition of n 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)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v∈V(G)}=k. Griggs and Yeh conjectured that λ(G)≤Δ2 for any simple graph with maximum degree Δ≥2. In this article, a problem in the proof of a theorem in Shao and Yeh (2005) [19], is addressed and the graph formed by the composition of n graphs is studied. We obtain bounds for the L(2,1)-labeling number for graphs of this type that is much better than what Griggs and Yeh conjectured for general graphs. As a corollary, the present bound is better than the result of Shiu et al. (2008) [21] for the composition of two graphs G1[G2] if , where ν2 and Δ2 are the number of vertices and maximum degree of G2 respectively.