KAIST Discrete Math Seminar

An L(j,k) labeling of a graph is a vertex labeling such that the difference of the labels of any two adjacent vertices is at least j and that of any two vertices of distance 2 is at least k. The minimum of the spans of all L(j,k)-labelings of G is denoted by . Recently Haque and Jha proved if G is a direct product of complete graphs, then coincide with the trivial lower bound $(N-1)k$ where N is the order of G when j/k is within a certain bound.

In this paper, we suggest a new labeling method of such a graph G. With this method, we extend the range of j/k such that holds. Moreover, we obtain an upper bound of for the remaining cases.