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

T. Calamoneri

Abstract

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

PDF Files

Journal version