The L(2,1)-Labeling Problem on Oriented Regular Grids

The L(2, 1)-labeling of a digraph G is a function f from the node set of G to the set of all non-negative integers such that vertical bar f(x) - f(y)vertical bar >= 2 if x and y are at distance 1, and f(x) not equal f(y) if x and y are at distance 2, where the distance from node x to node y is the length of a shortest dipath from x to y. The minimum over all L(2, 1)-labeling of G of the largest used label is called (lambda) over bar (G). In this paper, we study the L(2, 1)-labelings problem on squared, triangular and hexagonal grids and for them we compute the exact values of (lambda) over bar.