Improved bounds on the L(2,1)-number of direct and strong 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. This paper considers the graph formed by the direct product and the strong product of two graphs and gets better bounds than those of Klavžar and Špacapan with refined approaches.