A New Approach to the $L(2,1)$-Labeling of Some Products of Graphs
Wai Chee Shiu, Zhendong Shao, Kin‐Keung Poon, David Zhang · IEEE Transactions on Circuits & Systems II Express Briefs · 2008
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)|ges2 if d(x, y)=1 and |f(x)-f(y)|ges1 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):visinV(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 lambda-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.