Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427157 | Information Processing Letters | 2013 | 6 Pages |
•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.