L(3, 2, 1)-Labeling of the square of cycles

Given a graph G=(V,E), an L(3, 2, 1)-labeling of G consists of assigning an integer label from {0,…,σ(G)} to each node v such that it is at least 3 apart from the labels of the nodes adjacent to v, at least 2 apart from the labels of the nodes at distance 2 from v, and different from the labels of the nodes at a distance 3 from v. The L(3, 2, 1)-labeling problem consists of determining the minimum value of σ(G) for which such labeling exists; this number is denoted by λ(G) and is called the L(3, 2, 1)-labeling number of G. The problem has many possible applications in coding theory, signal processing, radar, data base management, communication network addressing, etc. and is NP-hard in general, while, it has been proved to be polynomially solvable for some classes of graphs. In this paper, we continue the study of the L(3, 2, 1)-number of the square of cycles Cn2, either closing or reducing the gap between the upper and lower bounds on the values of λ(Cn2) when n assumes several values. To prove our bounds, we introduce the new notions of labeling schemes associated with sets of consecutive labels and of forbidden labeling schemes.