Given a graph G and two positive integers p, q with p > q an L(p, q)-labeling of G is a function f from the vertex set V(G) to the set of all nonnegative integers such that vertical bar f (x) - f(y)vertical bar >= p if d(G)(x, y) = 1 and vertical bar f(x) - f(y)vertical bar >= q if d(G)(x, y) = 2. A k-L(p, q)-labeling is an L(p, q)-labeling such that no label is greater than k. The L(p, q)-labeling number of G, denoted by lambda(p,q)(G) is the smallest number k such that G has a k-L(p, q)-labeling. When considering the digraph D, we use lambda(p,q)* (D) in place of lambda(p,q) (D). We study the L(p, q) -labeling number of a digraph D in this paper. We find some relations between the L(p, q)-labeling number of a graph G and an orientation D of G, and give some results for the L(p, q)-labeling numbers of k-partite digraphs. We also study the L(p, q)-labeling numbers for those graphs D for which the underlying graphs are paths, cycles or trees.
展开▼