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 C n 2 , either closing or reducing the gap between the upper and lower bounds on the values of λ ( C n 2 ) 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.