Exact Solution of a Class of Frequency Assignment Problems in Regular Grids

T. Calamoneri, S. Caminiti, G. Fertin

Abstract

For any non negative real values h and k, an L(h,k)-labeling of a graph G=(V, E) is a function L:V -> R such that |L(u)-L(v)| >= h if (u,v) in E and |L(u)-L(v)| >= k if there exists w in V such that (u, w) in E and (w, v) in E. The \em span of an L(h,k)-labeling is the difference between the largest and the smallest value of L, so it is not restrictive to assume 0 as the smallest value of L. We denote by lambda_{h,k}(G) the smallest real lambda such that graph G has an L(h,k)-labeling of span lambda. The aim of the L(h,k)-problem is to satisfy the distance constraints using the minimum span. In this paper, we study L(h, k)-labeling problem on regular grids of degree 3, 4, 6, and 8 solving several open problems left in the literature.

PDF Files

Journal Version