A New Approach to the L(2, 1)-Labeling of Some Products of Graphs.

The frequency assignment problem is to assign a frequency which is a nonnegative integer to each radio transmitter so that interfering transmitters are assigned frequencies whose separation is not in a set of disallowed separations. This frequency assignment problem can be modelled with vertex labelings of graphs. An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that ∣f(x) - f(y)∣ ≥ 2 if d(x, y) = 1 and ∣f(x) - f(y)∣ ≥ 1 if d(x, y) = 2, where d(x, y) denotes the distance between x and y in G. The L(2, 1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v ∊ V(G)} = k. In this paper, we develop a dramatically new approach on the analysis of the adjacency matrices of the graphs to estimate the upper bounds of A-numbers of the four standard graph products. By the new approach, we can achieve more accurate results and with significant improvement of the previous bounds. [ABSTRACT FROM AUTHOR]