On (s,t)(s,t)-relaxed L(2,1)L(2,1)-labelings of the square lattice

• The (s,t)(s,t)-relaxed L(2,1)L(2,1)-labeling numbers of the square lattice are determined.
• Optimal (s,t)(s,t)-relaxed L(2,1)L(2,1)-labelings of the square lattice are presented.
• A series of channel assignment schemes are provided.

Suppose G is a graph. Let u be a vertex of G. A vertex v is called an i-neighbor of u   if dG(u,v)=idG(u,v)=i. A 1-neighbor of u is simply called a neighbor of u. Let s and t be two nonnegative integers. Suppose f is an assignment of nonnegative integers to the vertices of G. If the following three conditions are satisfied, then f   is called an (s,t)(s,t)-relaxed L(2,1)L(2,1)-labeling of G: (1) for any two adjacent vertices u and v of G  , f(u)≠f(v)f(u)≠f(v); (2) for any vertex u of G, there are at most s neighbors of u   receiving labels from {f(u)−1,f(u)+1}{f(u)−1,f(u)+1}; (3) for any vertex u of G, the number of 2-neighbors of u   assigned the label f(u)f(u) is at most t  . The minimum span of (s,t)(s,t)-relaxed L(2,1)L(2,1)-labelings of G   is called the (s,t)(s,t)-relaxed L(2,1)L(2,1)-labeling number of G  , denoted by λ2,1s,t(G). It is clear that λ2,10,0(G) is the so-called L(2,1)L(2,1)-labeling number of G  . In this paper, the (s,t)(s,t)-relaxed L(2,1)L(2,1)-labeling number of the square lattice is determined for each pair of two nonnegative integers s and t. And this provides a series of channel assignment schemes for the corresponding channel assignment problem on the square lattice.