The L(2, 1)-Labeling Problem on Oriented Regular Grids
Tiziana Calamoneri · The Computer Journal · 2011
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 |f(x)−f(y)| ≥ 2 if x and y are at distance 1, and f(x) ≠ 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 . 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 .