Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination

The L(2, 1)-labeling of a graph is an abstraction of the problem of assigni ng (integer) frequencies to radio transmitters, such that transmitters that are "close", receive different frequencies, and those that are "very close " receive frequencies that are further apart. The least span of frequencies in such a labeling is referred to as the lambda -number of the graph, Let n be odd greater than or equal to5, k = (n-3)/2 and let m(o,...,) m(k-1), m (k) each be a multiple of n. It is shown that lambda (C(m0)square...squareC (mk-1)) is equal to the theoretical minimum df n - 1, where C-r denotes a c ycle of length r and "square" denotes the Cartesian product of graphs. The scheme works for a vertex partition of C-m0 square...squareC(mk-1) squareC( k) into smallest (independent) dominating sets.