Optimal Channel Assignments for Lattices with Conditions at Distance Two
Jerrold R. Griggs, Xiaohua Teresa Jin · 2005
The problem of radio channel assignments with multiple levels of interference can be modeled using graph theory. Given a graph G, possibly infinite, and real numbers k/sub 1/, k/sub 2/, ..., k/sub p/ /spl ges/ 0, a L(k/sub 1/, k/sub 2/, ..., k/sub p/)-labeling of G assigns real numbers f(x) /spl ges/ 0 to the vertices x, such that the labels of vertices u and v differ by at least k/sub i/ if u and v are at distance i apart. We denote by /spl lambda/(G; k/sub 1/, k/sub 2/, ..., k/sub p/) the infimum span over such labelings f. We survey this new theory of real number labelings. When p - 2 it is enough to determine /spl lambda/(G; k, 1) for reals k /spl ges/ 0; which will be a piecewise linear function. We present the function for the square lattice (grid) and for the hexagonal lattice. For the triangular lattice, we have also solved it except for the range 1/2 /spl les/ k /spl les/ 4/5.