L(2, 1)-LABELING OF THE CARTESIAN AND STRONG PRODUCT OF TWO DIRECTED CYCLES.

The frequency assignment problem (FAP) is the assignment of frequencies to television and radio transmitters subject to restrictions imposed by the distance between transmitters. One of the graph theoretical models of FAP which is well elaborated is the concept of distance constrained labeling of graphs. Let G = (V, E) be a graph. For two vertices u and v of G, we denote d(u, v) the distance between u and v. An L(2, 1)-labeling for G is a function f: V → {0, 1, · · · } such that |f (u) - f (v)| ≥ 1 if d(u, v) = 2 and |f (u) - f (v)| ≥ 2 if d(u, v) = 1. The span of f is the difference between the largest and the smallest number of f (V). The λ-number for G, denoted by λ(G), is the minimum span over all L(2, 1)-labelings of G. In this paper, we study the λ-number of the Cartesian and strong product of two directed cycles. We show that for m, n ≥ 4 the λ-number of -→ Cm2 - → Cn is between 4 and 5. We also establish the λ-number of - → C m - → C n for m ≤ 10 and prove that the λ-number of the strong product of cycles - → C m - → C n is between 6 and 8 for m, n ≥ 48. [ABSTRACT FROM AUTHOR]