L(2,1)L(2,1)-labeling of oriented planar graphs

The L(2,1)L(2,1)-labeling of a digraph DD is a function ll from the vertex set of DD to the set of all nonnegative integers such that |l(x)−l(y)|≥2|l(x)−l(y)|≥2 if xx and yy are at distance 1, and l(x)≠l(y)l(x)≠l(y) if xx and yy are at distance 2, where the distance from vertex xx to vertex yy is the length of a shortest dipath from xx to yy. The minimum over all the L(2,1)L(2,1)-labelings of DD of the maximum used label is denoted λ→(D). If CC is a class of digraphs, the maximum λ→(D), over all D∈CD∈C is denoted λ→(C).In this paper we study the L(2,1)L(2,1)-labeling problem on oriented planar graphs providing some upper bounds on λ→. Then we focus on some specific subclasses of oriented planar graphs, improving the previous general bounds. Namely, for oriented prisms we compute the exact value of λ→, while for oriented Halin graphs and cacti we provide very close upper and lower bounds for λ→.