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)| ges 2 if d(x,y)=1 and |f(x)-f(y)| ges 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 lambda(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v isin 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 Klavzar and Spacapan with refined approaches.