ICTCS 2010 Version
T. Calamoneri and B. Sinaimeri
Abstract
The L(2,1)-labeling of a digraph D is a function l from the vertex set of D to the set of all nonnegative integers such that | l(x)-l(y) | \geq 2 if x and y are at distance 1, and l(x) \neq l(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 over all the L(2,1)-labelings of D of the maximum used label is denoted \vec{\lambda} (D). If C is a class of digraphs, the maximum \vec{\lambda} (D), over all D \in C is denoted \vec{\lambda} (C). In this paper we study the L(2,1)-labeling problem on oriented planar graphs providing some upper bounds on \vec{\lambda}. 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 \vec{\lambda}, while for oriented Halin graphs and cacti we provide very close upper and lower bounds for \vec{\lambda}. As side effects, we find upper bounds on the oriented chromatic number of cacti and the chromatic number of the (unoriented) squared graphs of oriented planar graphs.
PDF Files