L(j,k) labelings of direct product of complete graphs

2011/3/17 Thu 4:30PM-5:30PM (E6-1, Room 3433)

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 \(\lambda_k^j(G)\). Recently Haque and Jha proved if G is a direct product of complete graphs, then \(\lambda_k^j(G)\) 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 \(\lambda_k^j(G)=(N-1)k\) holds. Moreover, we obtain an upper bound of \(\lambda_k^j(G)\) for the remaining cases.