Distance Constrained Labelings of Strong Product of n General Graphs

摘要

The frequency assignment problem is to assign a frequency to each radio transmitter so that transmitters are assigned frequencies with allowed separations. Motivated by a variation of the frequency assignment problem, a fine graph theoretic model called L(2, 1)-labeling problem was put forward. 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 vertical bar f(x) - f(y)vertical bar >= 2 if d(x, y) = 1 and vertical bar f(x) - f (y)vertical bar >= 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 is an element of V (G)} = k. In this article, we study the problem of computing the L(2, 1)-labeling numbers on the graph formed by the strong product of any n general graphs. It is proved that the L(2, 1)-labeling numbers of the strong product of any n general graphs are much better than Griggs and Yeh conjectured.