NEW L( j, k)-LABELINGS FOR DIRECT PRODUCTS OF COMPLETE GRAPHS]

Abstract

An L(j, k)-labeling of a graph is a vertex labeling such that the difference between the labels of adjacent vertices is at least j and that between vertices separated by a distance 2 is at least k. The minimum of the spans of all L(j, k)-labelings of G is denoted by lambda(j)(k)(G). Recently, Hague and Jha [16] proved that if G is a multiple direct product of complete graphs, then lambda(j)(k)(G) coincides with the trivial lower bound (N - 1)k, where N is the order of G and j/k is within a certain bound. In this paper, we suggest a new labeling method for such a graph G. With this method, we extend the range of j/k such that lambda(j)(k)(G) = (N - 1)k holds. Moreover, we obtain the upper bound of lambda(j)(k)(G) for the remaining cases in the range j/k.