L(p,q)L(p,q) labeling of d-dimensional grids

In this paper, we address the problem of λλ labelings, that was introduced in the context of frequency assignment for telecommunication networks. In this model, stations within a given radius r must use frequencies that differ at least by a value p  , while stations that are within a larger radius r′>rr′>r must use frequencies that differ by at least another value q  . The aim is to minimize the span of frequencies used in the network. This can be modeled by a graph coloring problem, called the L(p,q)L(p,q) labeling, where one wants to label vertices of the graph G   modeling the network by integers in the range [0;M][0;M], in such a way that: (1) neighbors in G are assigned colors differing by at least p and (2) vertices at distance 2 in G are assigned colors differing by at least q, while minimizing the value of M. M   is then called the λλ number of G  , and is denoted by λqp(G).In this paper, we study the L(p,q)L(p,q) labeling for a specific class of networks, namely the d  -dimensional grid Gd=G[n1,n2,…,nd]Gd=G[n1,n2,…,nd]. We give bounds on the value of the λλ number of an L(p,q)L(p,q) labeling for any d⩾1d⩾1 and p,q⩾0p,q⩾0. Some of these results are optimal (namely, in the following cases: (1) p=0p=0, (2) q=0q=0, (3) q=1q=1 (4) p,q⩾1p,q⩾1, p=α·qp=α·q with 1⩽α⩽2d1⩽α⩽2d and (5) p⩾2dq+1p⩾2dq+1); when the results we obtain are not optimal, we observe that the bounds differ by an additive factor never exceeding 2q-22q-2. The optimal result we obtain in the case q=1q=1 answers an open problem stated by Dubhashi et al. [Channel assignment for wireless networks modelled as dd-dimensional square grids, in: Proceedings of the IWDC’02, International Workshop on Distributed Computing, Lecture Notes in Computer Science, vol. 2571, Springer, Berlin, 2002, pp. 130–141], and generalizes results from [A.A Bertossi, C.M. Pinotti, R.B. Tan, Efficient use of radio spectrum in wireless networks with channel separation between close stations, in: Proceedings of the DIAL MM for Mobility 2000, Fourth International Workshop on Discrete Algorithms and Methods for Mobile Computing and communications, 2000; A. Dubhashi, S. MVS, A. Pati, S. R., A.M. Shende, Channel assignment for wireless networks modelled as dd-dimensional square grids, in: Proceedings of the IWDC’02, International Workshop on Distributed Computing, Lecture Notes in Computer Science, vol. 2571, Springer, Berlin, 2002, pp. 130–141]. We also apply our results to get upper bounds for the L(p,q)L(p,q) labeling of d-dimensional hypercubes.