Distance two labeling on special family of graphs

Abstract

An L(2,1)-labeling of a graph G is an assignment f from the  vertex set V(G)  to the set of non-negative integers such that |f(x)-f(y)|\ge 2 if x and y are adjacent and |f(x)-f(y)|\ge 1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling  f:V(G) to {0,...,k}, and we are interested to find the minimum k among all possible assignments. This invariant, the minimum k, is known as the L(2,1)-labeling number or λ-number and is denoted by λ(G). In this paper, we determine the  λ-number for the coronas P_m \circ P_n,  P_m\circ C_n, P_m \circ K_{1,n} and P_m\circ W_n and find an upper bound of the λ-number for the corona G_1 \circ G_2 where G_1 and G_2 are any two graphs such that G_2 has an injective L(2,1)-labeling and also we prove that the bound is attainable when G_1 and G_2 are complete. Also we present an upper bound of the $\lambda$-number for the corona G_1 \circ G_2 where G_1 and G_2 are any two graphs.