L(2,1)-Labelings on the composition of n graphs

An -labeling of a graph is a function from the vertex set to the set of all nonnegative integers such that if and if , where denotes the distance between and in . The -labeling number of is the smallest number such that has an -labeling with . Griggs and Yeh conjectured that for any simple graph with maximum degree . In this article, a problem in the proof of a theorem in Shao and Yeh (2005) is addressed and the graph formed by the composition of graphs is studied. We obtain bounds for the -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) for the composition of two graphs if , where and are the number of vertices and maximum degree of respectively.